1. On the Planar Split Thickness of Graphs.
- Author
-
Eppstein, David, Kindermann, Philipp, Kobourov, Stephen, Liotta, Giuseppe, Lubiw, Anna, Maignan, Aude, Mondal, Debajyoti, Vosoughpour, Hamideh, Whitesides, Sue, and Wismath, Stephen
- Subjects
BIPARTITE graphs ,GEOMETRIC vertices ,APPROXIMATION theory ,COMPLETE graphs ,VISUALIZATION - Abstract
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 isk -splittable into a planar graph. Ak -split operation substitutes a vertexv by at mostk new vertices such that each neighbor ofv 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 verifyk -splittability in linear time, for a constantk . [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF