Chapter 4 **Embeddings combinatorially, contractibility of cycles, and the genus problem
**

Heawood [He890] introduced the problem of determining the smallest
number H(S) such that every map on the surface S can be colored in
H(S) colors in such a way that no two neighboring countries receive
the same color. This problem which we shall treat in more detail in
Chapter 8 can be reduced to the problem
of deciding which complete graphs can be embedded in S.
This is a special case of the **genus problem**, one of the
fundamental problems listed by Garey and Johnson [GJ79]: Given a graph
G, determine the minimum genus of a surface in which G can be embedded.
The solution of the Heawood problem obtained by Ringel and
Youngs [RY68, Ri74] involves the calculation of
the genera of the complete graphs.

Embeddings and the genus of graphs are studied in Section 4.4. It is shown that the genus problem is as difficult as many other well-known hard combinatorial problems. More precisely, the decision version of the genus problem is NP-complete as shown by Thomassen [Th89]. In the last section we treat the maximum genus of graphs which is better understood than the (minimum) genus.

The calculation of genera of various classes of graphs are extensively treated in other books on topological graph theory. The reader is referred to the monographs by Ringel [Ri74], White [Wh73], and by Gross and Tucker [GT87].