Universal Geometric Graphs

Abstract

We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H. Our main result is that there exists a geometric graph with n vertices and O(nlog n) edges that is universal for n-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an n-vertex graph with O(nlog n) edges that contains every n-vertex forest as a subgraph. Our O(nlog n) bound on the number of edges is asymptotically optimal. We also prove that, for every h> 0, every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2-1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlog n) edges that is universal for n-vertex caterpillars.