The genus g (G) of a graph G is the smallest number g such that G can be embedded on the orientable surface of genus g. Given a graph G and a natural number k one may ask: Is g (G) I k? This problem, called the graph genus problem, is one of the remaining basic open problems, listed by Garey and Johnson 121, for which there is neither a polynomially bounded algorithm nor a proof that the problem is NP-complete. For k fixed, Filotti ei al.[l] described a polynomially bounded algorithm for the graph genus problem. Such an algorithm also follows from the Robertson-Seymour theory on minors [5]. The author [6] proved that a given embedding is of minimum genus provided all the noncontractible cycles are longer than all facial walks.[6] also contains both a polynomially bounded algorithm for deciding if a given embedding has this property and also a polynomially bounded algorithm for deciding if a 2-connected graph has an embedding of this type.

However, we shall here prove that the graph genus problem is NP-complete. We show that the problem of deciding if the independence number a (G)(that is, the cardinal&y of a largest set of pairwise nonadjacent vertices in the graph G) is greater than k (a problem which is known to be NP-complete [2]) can be reduced, in polynomial time, to the graph genus problem. The reduction is as follows: We let G’be obtained from G by replacing each edge xy by a large double wheel. That is, we delete xy and add a long cycle C and all edges between C and {x, y}. We let G” be obtained from G’by adding a new vertex and joining it to a vertex in each