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.
A rich body of literature considers the planarization of non-planar graphs via @cite_13 @cite_9 @cite_1 @cite_19 . Here a is one of our 2-split operations. These results focus on minimizing the , i.e., the total number of vertex splits to obtain a planar graph. Tight bounds on the splitting number are known for complete graphs @cite_9 and complete bipartite graphs @cite_22 @cite_15 , but for general graphs, the problem of determining the splitting number of a graph is NP-hard @cite_13 . Note that upper bounding the splitting number does not necessarily guarantee any good upper bound on the planar split thickness, e.g., see .
@cite_22 @cite_9 @cite_1 @cite_19 @cite_15 @cite_13
1536302196 2111635834 2065149403 2154213027
We consider two graph invariants that are used as a measure of nonplanarity: the splitting number of a graph and the size of a maximum planar subgraph. The splitting number of a graph G is the smallest integer k ≥ 0, such that a planar graph can be obtained from G by k splitting operations. Such operation replaces a vertex v by two nonadjacent vertices v1 and v2, and attaches the neighbors of v either to v1 or to v2. We prove that the splitting number decision problem is NP-complete, even when restricted to cubic graphs. We obtain as a consequence that planar subgraph remains NP-complete when restricted to cubic graphs. Note that NP-completeness for cubic graphs also implies NP-completeness for graphs not containing a subdivision of K5 as a subgraph. Given a nite, undirected, simple graph G, we are concerned with operations on G that transform it into a planar graph. We give a survey of results about such operations and related graph parameters. While there are many algorithmic results about planarization through edge deletion, the results about vertex splitting, thickness, and crossing number are mostly of a structural nature. We also include a brief section on vertex deletion. We do not consider parallel algorithms, nor do we deal with on-line algorithms. If a given graphG can be obtained bys vertex identifications from a suitable planar graph ands is the minimum number for which this is possible thens is called the splitting number ofG. Here a formula for the splitting number of the complete graph is derived. We consider the following graph labeling problem, introduced by (J. Y-T. Leung, O. Vornberger, and J. D. Witthoff, On some variants of the bandwidth minimization problem. SIAM J. Comput. 13 (1984) 650–667). Let G be a graph of order n, and f a bijection from V(G) to the integers 1 through n. Let |f|, and define s(G), the separation number of G, to be the maximum of |f| among all such bijections f. We first derive some basic relations between s(G) and other graph parameters. Using a general strategy for analyzing separation number in bipartite graphs, we obtain exact values for certain classes of forests and asymptotically optimal lower bounds for grids and hypercubes.