×

On the complexity of the approximation of nonplanarity parameters for cubic graphs. (English) Zbl 1042.05092

Summary: Let \(G=(V,E)\) be a simple graph. The NON-PLANAR DELETION problem consists in finding a smallest subset \(E'\) of \(E\) such that \(H=(V,E\setminus E')\) is a planar graph. The SPLITTING NUMBER problem consists in finding the smallest integer \(k \geqslant 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.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, in Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS’92, pp. 14-23.; S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and hardness of approximation problems, in Proceedings of the IEEE Symposium on Foundations of Computer Science, FOCS’92, pp. 14-23. · Zbl 0977.68539
[2] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), American Elsevier Publishing Co., Inc: American Elsevier Publishing Co., Inc New York · Zbl 1134.05001
[3] Cǎlinescu, G.; Fernandes, C. G.; Finkler, U.; Karloff, H., A better approximation algorithm for finding planar subgraphs, J. Algorithms, 27, 269-302 (1998) · Zbl 0919.68093
[4] Faria, L.; de Figueiredo, C. M.H.; Mendonça, C. F.X., Splitting number is NP-complete, Discrete Appl. Math, 108, 1-2, 65-83 (2001) · Zbl 0969.68110
[5] Papadimitriou, C. H.; Yannakakis, M., Optimization, approximation, and complexity classes, J. Comput. System Sci, 43, 425-440 (1991) · Zbl 0765.68036
[6] Tutte, W. T., Connectivity in Graphs (1966), University of Toronto Press: University of Toronto Press Toronto · Zbl 0146.45603
[7] Yannakakis, M., Edge-deletion problems, SIAM J. Comput, 10, 297-309 (1981) · Zbl 0468.05043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.