期刊
ALGORITHMICA
卷 80, 期 3, 页码 977-994出版社
SPRINGER
DOI: 10.1007/s00453-017-0328-y
关键词
Planarity; Splittable; Thickness; Graph drawing; Graph theory; Complete graphs; Genus-1 graphs; NP-hardness; Approximation; Fixed-parameter tractable
资金
- NSF [1228639]
- PRIN Italian National Research Project [2012C4E3KT]
- PEPS egalite project
- NSERC
- Direct For Computer & Info Scie & Enginr [1228639] Funding Source: National Science Foundation
- Division Of Computer and Network Systems [1228639] Funding Source: National Science Foundation
Motivated by applications in graph drawing and information visualization, we examine the planar split thickness of a graph, that is, the smallest k such that the graph is k-splittable into a planar graph. A k-split operation substitutes a vertex v by at most k new vertices such that each neighbor of v is 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 verify k-splittability in linear time, for a constant k.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据