Abstract
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, even 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 also implies NP-completeness for graphs not containing a subdivision of K 5 as a subgraph.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the 3rd. ACM Symposium on Theory of Computing, pp. 151–158. Association for Computing Machinery, New York (1971)
Eades, P., Mendonça, C.F.X.: Heuristics for Planarization by Vertex Splitting. In: Proc. ALCOM Int. Workshop on Graph Drawing, GD 1993, pp. 83–85 (1993)
Eades, P., Mendonça, C.F.X.: Vertex Splitting and Tension-Free Layout. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 202–211. Springer, Heidelberg (1996)
Faria, L., Figueiredo, C.M.H., Mendonça, C.F.X.: The splitting number of the 4-cube. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 141–150. Springer, Heidelberg (1998)
Faria, L., Figueiredo, C.M.H., Mendonça, C.F.X.: Splitting number is NP-Complete, Technical Report ES-443/97, COPPE/UFRJ, Brazil (1997), Available at ftp://ftp.cos.ufrj.br/pub/tech_reps/es44397.ps.gz
Hartfield, N., Jackson, B., Ringel, G.: The splitting number of the complete graph. Graphs and Combinatorics 1, 311–329 (1985)
Hopcroft, J.E., Tarjan, R.E.: Efficient Planarity Testing. J. ACM 21, 549–568 (1974)
Jackson, B., Ringel, G.: The splitting number of complete bipartite graphs. Arch. Math. 42, 178–184 (1984)
Kuratowski, K.: Sur le problème des courbes gauches en topologie. Fund. Math. 15, 271–283 (1930)
Liebers, A.: Methods for Planarizing Graphs - A Survey and Annotated Bibliography (1996), Available at ftp://ftp.informatik.uni-konstanz.de/pub/preprints/1996/preprint-012.ps.Z
Liu, P.C., Geldmacher, R.C.: On the deletion of nonplanar edges of a graph. Cong. Num. 24, 727–738 (1979)
Mendonça, C.F.X.: A Layout System for Information System Diagrams, PhD thesis, Univ. of Queensland, Australia (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Faria, L., de Figueiredo, C.M.H., Mendonça, C.F.X. (1998). Splitting Number is NP-Complete. In: Hromkovič, J., Sýkora, O. (eds) Graph-Theoretic Concepts in Computer Science. WG 1998. Lecture Notes in Computer Science, vol 1517. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10692760_23
Download citation
DOI: https://doi.org/10.1007/10692760_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65195-6
Online ISBN: 978-3-540-49494-2
eBook Packages: Springer Book Archive