%0 Conference Paper %1 ekkllmmvww-opstg-latin16 %A Eppstein, Davin %A Kindermann, Philipp %A Liotta, Giuseppe %A Lubiw, Anna %A Maignan, Aude %A Mondal, Debajyoti %A Vosoughpour, Hamideh %A Whitesides, Sue %A Wismath, Stephen %B Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN'16) %D 2016 %E Kranakis, Evangelos %E Navarro, Gonzalo %E Chávez, Edgar %I Springer-Verlag %K myown planar split thickness %P 403--415 %R 10.1007/978-3-662-49529-2_30 %T On the Planar Split Thickness of Graphs %V 9644 %X 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 and complete bipartite 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-splittablity in linear time, for a constant k.

@inproceedings{ekkllmmvww-opstg-latin16, 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 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 and complete bipartite 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-splittablity in linear time, for a constant k.}, added-at = {2015-09-10T15:14:05.000+0200}, arxiv = {https://arxiv.org/abs/1512.04839}, author = {Eppstein, Davin and Kindermann, Philipp and Liotta, Giuseppe and Lubiw, Anna and Maignan, Aude and Mondal, Debajyoti and Vosoughpour, Hamideh and Whitesides, Sue and Wismath, Stephen}, biburl = {https://www.bibsonomy.org/bibtex/2b9a2414e346c106441299f4fa0605d9c/kindermann}, booktitle = {Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN'16)}, doi = {10.1007/978-3-662-49529-2_30}, editor = {Kranakis, Evangelos and Navarro, Gonzalo and Ch{\'{a}}vez, Edgar}, interhash = {1c709ece22195d008d4e5dcfc219f0af}, intrahash = {b9a2414e346c106441299f4fa0605d9c}, keywords = {myown planar split thickness}, month = apr, pages = {403--415}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/kindermann/slides/2016-hag-split_thickness.pdf}, timestamp = {2018-09-18T06:49:48.000+0200}, title = {On the Planar Split Thickness of Graphs }, volume = 9644, year = 2016 }