Universal Geometric Graphs

DOI10.1007/978-3-030-60440-0_14MaRDI QIDQ6343300arXivFDO

Authors Fabrizio Frati, Csaba D. Tóth

Publication date 19 June 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-60440-0_14

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.CGmath.CO

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 emph{universal} for a class $mathcalH$ of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in $mathcalH$. Our main result is that there exists a geometric graph with $n$ vertices and $O(nlogn)$ 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(nlogn)$ edges that contains every $n$-vertex forest as a subgraph. Our $O(nlogn)$ bound on the number of edges cannot be improved, even if more than $n$ vertices are allowed. We also prove that, for every positive integer $h$, every $n$-vertex convex geometric graph that is universal for $n$-vertex outerplanar graphs has a near-quadratic number of edges, namely $Omeg{a}_h(n^{2-1/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(nlogn)$ edges that is universal for $n$-vertex caterpillars.

This page was built for publication: Universal Geometric Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6343300)