zbMATH — the first resource for mathematics

Crossing number is NP-complete. (English) Zbl 0536.05016
The general crossing number decision problem is defined as follows: ”Given a graph G (multiple edges are allowed) and an integer k, is the crossing number of G less than or equal to k?” The authors prove that the crossing number decision problem is NP-complete, and hence likely to be intractable. By a simple argument it is shown that crossing number is in NP. To prove the NP-completeness, the known NP-complete problem of optimal linear arrangement (”Given a graph \(G=(V,E)\) and an integer k, is there a bijection \(f:V\to \{1,2,...,| V| \}\) such that \(\sum_{(u,v)\in E}| f(u)-f(v)| \leq k\)?”) is shown to be polynomially transformable to crossing number.
Reviewer: J.Širáň

05C10 Planar graphs; geometric and topological aspects of graph theory
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039
[2] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. J., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237, (1976) · Zbl 0338.05120
[3] Hopcroft, J. E.; Tarjan, R. E., Efficient planarity testing, J. Assoc. Comput. Mach., 21, 549, (1974) · Zbl 0307.68025
[4] New lower bound techniques for VLSIProc. 22nd Annual Symposium on Foundations of Computer ScienceIEEE Computer SocietyLong Beach, CA1981112
[5] Sinden, F. W., Topology of thin film circuits, Bell Syst. Tech. J., XLV, 1639, (1966) · Zbl 0144.45601
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.