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