Universal Geometric Graphs
METADATA ONLY
Author / Producer
Date
2020
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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.
Permanent link
Publication status
published
External links
Book title
Graph-Theoretic Concepts in Computer Science
Journal / series
Volume
12301
Pages / Article No.
174 - 186
Publisher
Springer
Event
46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020) (virtual)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
Notes
Due to the Coronavirus (COVID-19) the conference was conducted virtually.
Funding
171681 - Arrangements and Drawings (ArrDra) (SNF)