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.
Users
Please
log in to take part in the discussion (add own reviews or comments).