Carsten Thomassen [T] has shown that the graph genus problem is NP-complete. That is, given a graph G and a natural number k, it is apparently hard to determine if G embeds on the sphere with k handles. The following question asks if the problem is still hard when looking only at cubic graphs.

Question: Given a 3-regular graph G and a non-negative integer k, is it NP-complete to determine if G embeds in the sphere with k handles?

It is known that the crossing problem is NP-complete. [[Note by Dan Archdeacon: I thought this was in Garey and Johnson [GJ], but may be wrong. I do not know the reference.]] 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 both problems are NP-complete.]

[GJ] M.\ Garey and D.\ Johnson, Computers and intractability, A guide to the theory of NP-completeness W.H. Freeman, San Francisco CA (1979).

[T] C. Thomassen, The graph genus problem is NP-complete, J. Algorithms 10 (1989) 568-576.

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