splitting number is NP-complete

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₁ and v₂, and attaches the neighbors of v either to v₁ or to v₂. 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₅ as a subgraph.