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 v_1 and v_2, and attaches the neighbors of v either to v_1 or to v_2. We prove that the SPLITTING NUMBER decision problem is NP-complete 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 implies NP-completeness for graphs not containing a subdivision of K_5 as a subgraph.
展开▼
