Optimal node-degree bounds for the complexity of nonplanarity parameters
Celina M.H. de Figueiredo, Luérbio Faria, Candido Ferreira Xavier de Mendonça · 1999
We prove that both the NP-completeness of the nonplanar deletion decision problem and the Max SNP-hardness of the nonplanar deletion problem remain true even for cubic graphs. We prove that the class of graphs with splitting number less than or equal to a fixed k is minor closed, which implies the existence of a corresponding polynomial-time recognition algorithm. 1 Introduction. A natural question in the study of the complexity of a graph-theoretical decision problem is to determine the best possible bounds on the node degrees for which the problem remains NP-complete. Yannakakis [11] considered the complexity of edge-deletion decision problems and obtained corresponding best possible node-degree bounds for the NP-completeness of the edge-deletion bipartite problem and of the edge-deletion comparability graph problem. The edge-deletion planar graph problem is also known as nonplanar deletion: given a graph G = (V; E), produce a smallest subset L ` E such that (V; EnL) is planar. The...