Chapter 4 Embeddings combinatorially, contractibility of cycles, and the genus problem
By Theorems 3.2.4 and 3.3.1, a cellular embedding is uniquely determined by its rotation system (or embedding scheme). Motivated by this result we now define an embedding of a connected graph to be a rotation system (or an embedding scheme) of the graph. So from now on, an embedding is a purely combinatorial object and it makes sense to speak of computational aspects of embeddings. We derive some basic properties of embeddings and describe techniques which enable us still to use geometric intuition. We then treat some classical problems mentioned below.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].