论文标题
通用几何图
Universal Geometric Graphs
论文作者
论文摘要
我们介绍并研究了构建几何图的问题，这些几何图几乎没有顶点和边缘，并且对于平面图或某些平面图的一类是通用的；对于平面图的类$ \ Mathcal h $，如果它包含$ \ Mathcal H $中每个图的每个图形，则是平面图的$ \ Mathcal H $的几何图。 我们的主要结果是有一个带有$ n $顶点的几何图和$ o（n \ log n）$ edges，对于$ n $ vertex Forests来说是通用的；这扩展到了Chung和Graham的几何设置，它是一个众所周知的图理论结果，该结果指出，存在$ n $ vertex图，上面有$ o（n \ log n）$ edges，其中包含每$ n $ vertex Forest作为子图。即使允许超过$ n $的顶点，我们的$ O（n \ log n）$也无法提高边缘数量。 我们还证明，对于每个正整数$ h $，每个$ n $ vertex suvex几何图都具有通用的$ n $ vertex ofterplanar图，具有接近二次的边缘，即$ω__h（n^{2-1/h}）$;这几乎与$ n $ vertex完整凸几何图给出的琐事$ o（n^2）$上限匹配。 最后，我们证明存在$ n $ -VERTEX凸面几何图，带有$ N $ VERTICES和$ O（n \ log n）$ edges，对于$ n $ vertex caterpillars而言是通用的。
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 $\mathcal H$ of planar graphs if it contains an embedding, i.e., 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(n \log 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(n \log n)$ edges that contains every $n$-vertex forest as a subgraph. Our $O(n \log n)$ 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 $Ω_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(n \log n)$ edges that is universal for $n$-vertex caterpillars.
