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