On the complexity of the approximation of nonplanarity parameters for cubic graphs Original Research Article

Let G=(V,E) be a simple graph. The NON-PLANAR DELETION problem consists in finding a smallest subset E′⊂E such that H=(V,E⧹E′) is a planar graph. The SPLITTING NUMBER problem consists in finding the smallest integer k⩾0, such that a planar graph H can be defined from G by k vertex splitting operations. We establish the Max SNP-hardness of SPLITTING NUMBER and NON-PLANAR DELETION problems for cubic graphs.