Veröffentlichung

Titel:

On the Planar Split Thickness of Graphs

AutorInnen:

David Eppstein
Philipp Kindermann
Stephen Kobourov
Giuseppe Liotta
Anna Lubiw
Aude Maignan
Debajyoti Mondal
Hamideh Vosoughpour
Sue Whitesides
Stephen Wismath

Kategorie:

Konferenzbandbeiträge

erschienen in:

Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN'16), pp. 403-415

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.

Download:

Springer

BibTeX-Eintrag:

@InProceedings{ekkllmmvww-opstg-latin16, Title = {On the Planar Split Thickness of Graphs}, Author = {David Eppstein and Philipp Kindermann and Stephen Kobourov and Giuseppe Liotta and Anna Lubiw and Aude Maignan and Debajyoti Mondal and Hamideh Vosoughpour and Sue Whitesides and Stephen Wismath}, Booktitle = {Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN’16)}, Year = {2016}, Editor = {E. Kranakis and G. Navarro}, Note = {To appear}, Publisher = {Springer}, Series = {Lecture Notes in Computer Science}, 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$.} }