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".
[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 firstname.lastname@example.org and to email@example.com
August, 1995. Modified November 1998