Finding the Crossing Number of a Cubic Graph (Solved)
The original statement of this problem was:
It is known that the crossing problem is NP-complete [GJ]. That is, given a graph G and a natural number k, it is apparently hard to determine if G embeds in the plane with exactly k crossings. The construction uses non-cubic graphs, leaving open the possibility that the corresponding problem is easy for cubic graphs.
Question: Given a 3-regular graph G and a non-negative integer k, is it NP-complete to determine if there is a drawing of G in the plane with exactly k crossings?
As far as I know, these questions originated with me, although it's likely that others have thought of them.
[Note added by Dan Archdeacon: I conjecture that this problem is NP-complete. An earlier version of this page included a related problem on the complexity of finding the genus of a cubic graph. That problem is now solved, see "Finding the genus of a cubic graph".]
Petr Hlineny reports that he has proven that determining the crossing number is NP-complete, even for cubic graphs. Details are to follow.
[GJ] M. Garey and D. Johnson, Crossing number is NP-complete, SIAM J. Alg. Disc. Meth. 4 (1983) 312-316
Submitted by: Bruce Richter, Department of Mathematics and Statistics, Carleton University, Ottawa, Canada.
August, 1995. Modified November 1998, & December 2003.