On the Planar Split Thickness of Graphs
On the Planar Split Thickness of Graphs
复制标题
DOI：
10.1007/s00453-017-0328-y
复制
发表时间：
2015-12
期刊：
影响因子：
1.1
通讯作者：
D. Eppstein;Philipp Kindermann;S. Kobourov;G. Liotta;A. Lubiw;A. Maignan;Debajyoti Mondal;H. Vosoughpour;S. Whitesides;S. Wismath
中科院分区：
文献类型：
--
作者：
D. Eppstein;Philipp Kindermann;S. Kobourov;G. Liotta;A. Lubiw;A. Maignan;Debajyoti Mondal;H. Vosoughpour;S. Whitesides;S. Wismath
受图形绘制和信息可视化应用的启发，我们研究了图的平面分裂厚度，即使图可分裂为平面图的最小厚度。ak-分裂操作在最多已知顶点处替换一个顶点，使得每个相邻顶点至少与一个新顶点相连。我们首先研究了完全图、完全二部图、多部图、有界度图和亏格1图的平面分裂厚度。然后，我们证明了它是NP-难识别的图是2-splittable到一个平面图，并表明，一个可以近似的平面分裂厚度的一个图内的常数因子。如果树宽是有界的，那么我们甚至可以在线性时间内验证k-可分裂性，对于常数k。
Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallestksuch that the graph isk-splittable into a planar graph. Ak-split operation substitutes a vertexvby at mostknew vertices such that each neighbor ofvis connected to at least one of the new vertices. We first examine the planar split thickness of complete graphs, complete bipartite graphs, multipartite graphs, bounded degree graphs, and genus-1 graphs. We then prove that it is NP-hard to recognize graphs that are 2-splittable into a planar graph, and show that one can approximate the planar split thickness of a graph within a constant factor. If the treewidth is bounded, then we can even verifyk-splittability in linear time, for a constantk.