Universal geometric graphs

Source abstract

Abstract We extend the notion of universal graphs to a geometric setting. A geometric graph is universal for a class $\mathcal H$ of planar graphs if it contains an embedding, that is, a crossing-free drawing, of every graph in $\mathcal H$ . Our main result is that there exists a geometric graph with $n$ vertices and $O\!\left(n \log n\right)$ edges that is universal for $n$ -vertex forests; this generalises a well-known result by Chung and Graham, which states that there exists an (abstract) graph with $n$ vertices and $O\!\left(n \log n\right)$ edges that contains every $n$ -vertex forest as a subgraph. The upper bound of $O\!\left(n \log n\right)$ edges cannot be improved, even if more than $n$ vertices are allowed. We also prove that every $n$ -vertex convex geometric graph that is universal for $n$ -vertex outerplanar graphs has a near-quadratic number of edges, namely $\Omega _h(n^{2-1/h})$ , for every positive integer $h$ ; this almost matches the trivial $O(n^2)$ upper bound given by the $n$ -vertex complete convex geometric graph. Finally, we prove that there exists an $n$ -vertex convex geometric graph with $n$ vertices and $O\!\left(n \log n\right)$ edges that is universal for $n$ -vertex caterpillars.