Drawing Planar Graphs with Many Collinear Vertices
Drawing Planar Graphs with Many Collinear Vertices
复制标题
绘制具有许多共线顶点的平面图
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Vincenzo Roselli
中科院分区：
文献类型：
--
作者：
G. D. Lozzo;V. Dujmović;Fabrizio Frati;T. Mchedlidze;Vincenzo Roselli
给定一个平面图G，G的一个平面直线图中共线顶点的最大数目是多少？这个问题存在于几个图形绘制问题的核心，包括通用点子集，解开和列平面性。已知如下结果：每个n-顶点平面图都有一个顶点共线的平面直线图（varOmega（sqrt{n}））;对于每个n，都有一个平面直线图（varTheta（n））共线;每个树宽不超过2的n-顶点平面图都有一个顶点共线的平面直线图（varTheta（n））.我们扩展的线性约束的树宽最多为3的平面图和三连通三次平面图，部分回答了两个问题所提出的拉夫斯基和Verbitsky。类似的结果是不可能的所有有界树宽或有界度平面图。对于树宽至多为3的平面图，我们的结果也意味着上述所有其他绘图问题的渐近紧界。
Given a planar graph G, what is the maximum number of collinear vertices in a planar straight-line drawing of G? This problem resides at the core of several graph drawing problems, including universal point subsets, untangling, and column planarity. The following results are known: Every n-vertex planar graph has a planar straight-line drawing with (varOmega (sqrt{n})) collinear vertices; for every n, there is an n-vertex planar graph whose every planar straight-line drawinghas (O(n^{0.986})) collinear vertices; every n-vertex planar graph of treewidth at most two has a planar straight-line drawingwith (varTheta (n)) collinear vertices. We extend the linear bound to planar graphs of treewidth at most three and to triconnected cubic planar graphs, partially answering two problems posed by Ravsky and Verbitsky. Similar results are not possible for all bounded treewidth or bounded degree planar graphs. For planar graphs of treewidth at most three, our results also imply asymptotically tight bounds for all of the other above mentioned graph drawing problems.