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".]

Solution:

Petr Hlineny reports that he has proven that determining the crossing number is NP-complete, even for cubic graphs. Details are to follow.

References:

[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.

Send comments to dan.archdeacon@uvm.edu and to bruce_richter@carleton.ca

August, 1995. Modified November 1998, & December 2003.