Finding the Genus of a Cubic Graph

The problem below has been solved by Carsten Thomassen. The problem is NP-complete [T2].

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

In an earlier version of this page this problem was listed along with the still unsolved "Finding the crossing number of a cubic graph".

References:

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

[T2] C. Thomassen, The genus problem for cubic graphs, *J. Combin. Th. Ser. B* **69** (1997) 52-58.

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