Chapter 3   Surfaces

 In this chapter we establish some basic tools for graphs embedded on surfaces. We restrict ourselves to compact 2-dimensional surfaces without boundary. These are compact connected Hausdorff topological spaces in which every point has a neighborhood that is homeomorphic to the plane R2. In Section 3.1 we present a simple rigorous proof (due to Thomassen [Th92] of the fact that every surface is homeomorphic to a triangulated surface. Other available proofs of this result are complicated and appeal to geometric intuition. Perhaps it is difficult to follow some of the details but the proof is conceptually very simple since it merely consists of repeated use of the Jordan-Schoenflies Theorem. The surface classification theorem, which we prove next, says that every surface is homeomorphic to a space obtained from the sphere by adding handles and crosscaps. One of the first complete proofs of this fundamental result was given by Kerekjarto [Ke23]. The proof presented in Section 3.1 is very short and follows [Th92]. It differs from other proofs in the literature in that it uses no topological results, not even the Jordan Curve Theorem (except for polygonal simple closed curves in the plane). In particular, it does not use Euler's formula (which includes the Jordan Curve Theorem). Instead, Euler's formula is a by-product of the proof.

After obtaining the surface classification theorem, it is shown that every orientable graph embedding, whose faces are all homeomorphic to an open disc in the plane, can be described combinatorially, up to homeomorphism, by the local rotations at each vertex. A similar description exists also for embeddings of graphs into nonorientable surfaces. Again, this is proved rigorously without appealing to geometric intuition.

Inspired by the possibility of describing embeddings of graphs combinatorially, we define in Chapter 4 an embedding as a collection of local rotations in the orientable case and, more generally, an embedding scheme in the nonorientable case. In the remaining part of the book we treat embeddings in this purely combinatorial framework.