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: | Artikel in Zeitschriften |
erschienen in: | Algorithmica, Special Issue on Selected Papers from LATIN'16, 2017, pp. 1-18. Online first. |
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 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. |
Download: | Journal Website |
BibTeX-Eintrag: | @Article{ekkllmmvww-opstg-A17, 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}, title = {On the Planar Split Thickness of Graphs}, journal = {Algorithmica}, year = {2017}, pages = {1--18}, note = {Special Issue on Selected Papers from LATIN 2016. Online first.}, 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 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$.}, doi = {10.1007/s00453-017-0328-y}, } |