Skip to Main content Skip to Navigation
Conference papers

On the Planar Split Thickness of Graphs

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.
Document type :
Conference papers
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-01326779
Contributor : Aude Maignan <>
Submitted on : Sunday, June 5, 2016 - 5:31:17 PM
Last modification on : Tuesday, May 11, 2021 - 11:37:28 AM

Links full text

Identifiers

Collections

Citation

David Eppstein, Philipp Kindermann, Stephen Kobourov, Giuseppe Liotta, Anna Lubiw, et al.. On the Planar Split Thickness of Graphs. LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Apr 2016, Ensenada, Mexico. pp.403-415, ⟨10.1007/978-3-662-49529-2_30⟩. ⟨hal-01326779⟩

Share

Metrics

Record views

439