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.
Knauer and Ueckerdt @cite_29 studied the which is equivalent to our problem and stated several results for splitting graphs into a star forest, a caterpillar forest, or an interval graph. They showed that planar graphs are 4-splittable into a star forest, and planar bipartite graphs as well as outerplanar graphs are 3-splittable into a star forest. It follows from Scheinerman and West @cite_3 that planar graphs are 3-splittable into an interval graph and 4-splittable into a caterpillar forest, while outerplanar graphs are 2-splittable into an interval graph.
@cite_29 @cite_3
2139849594 2071261821
We consider the problem of covering an input graph H with graphs from a fixed covering class G . The classical covering number of H with respect to G is the minimum number of graphs from G needed to cover the edges of H without covering non-edges of H . We introduce a unifying notion of three covering parameters with respect to G , two of which are novel concepts only considered in special cases before: the local and the folded covering number. Each parameter measures "how far" H is from G in a different way. Whereas the folded covering number has been investigated thoroughly for some covering classes, e.g.,?interval graphs and planar graphs, the local covering number has received little attention.We provide new bounds on each covering number with respect to the following covering classes: linear forests, star forests, caterpillar forests, and interval graphs. The classical graph parameters that result this way are interval number, track number, linear arboricity, star arboricity, and caterpillar arboricity. As input graphs we consider graphs of bounded degeneracy, bounded degree, bounded tree-width or bounded simple tree-width, as well as outerplanar, planar bipartite, and planar graphs. For several pairs of an input class and a covering class we determine exactly the maximum ordinary, local, and folded covering number of an input graph with respect to that covering class. Abstract Suppose each vertex of a graph G is assigned a subset of the real line consisting of at most t closed intervals. This assignment is called a t -interval representation of G when vertex v is adjacent to vertex w if and only if some interval for v intersects some interval for w . The interval number i ( G ) of a graph G is the smallest number t such that G has a t -interval representation. It is proved that i ( G ) ≤ 3 whenever G is planar and that this bound is the best possible. The related concepts of displayed interval number and depth- r interval number are discussed and their maximum values for certain classes of planar graphs are found.