There are numerous examples showing the importance of planar graphs (or, equivalently, graphs on the sphere) in discrete mathematics. One beautiful example is Steinitz' theorem that the graphs (or 1-skeletons) of the 3-dimentional polytopes are precisely the 3-connected planar graphs. Planar graphs and their duals form an important link between graphs and matroids.
Also graphs on higher surfaces are useful. Consider, for example, the following seemingly simple question of characterizing those graphs that do not contain two disjoint cycles of odd length. This problem was solved by Lovasz using Seymour's deep characterization of the regular matroids. The interesting graphs in this family are those which can be drawn in the projective plane such that all faces are bounded by even cycles. The fact that no such graph has two disjoint odd cycles could be proved by a tedious combinatorial argument. The natural proof, however, is merely a reference to the fact that the projective plane has no two disjoint noncontractible cycles, an immediate consequence of the classification theorem.
Graphs on surfaces play a central role in the deep Robertson-Seymour theory on graph minors. One of the main results of Robertson and Seymour is the following: Any infinite collection of graphs contains two graphs, say G and H, such that H is a minor of G, that is, H can be obtained from G by contracting and deleting edges and deleting isolated vertices. An important consequence (and source of motivation) of this impressive result is an extension of Kuratowski's theorem to higher surfaces: For every fixed surface S, there is a finite collection Forb0(S) of graphs that cannot be drawn on S such that any graph G can be drawn on S if and only if G has no graph in Forb0(S) as a minor.
The literature on graphs on surfaces is immense and has already been treated in some monographs. Ringel [Ri74] presented the complete proof of the Heawood conjecture. White [Wh73] emphasized the algebraic aspects, and so did Gross and Tucker [GT87] who also discussed voltage and current graphs. Tutte [Tu84] and Bonnington and Little [BL95] treated graphs on surfaces from a purely combinatorial point of view. Our work has only little overlap with these books and treats in more depth several more recent achievements in topological graph theory.
Graphs on surfaces can be described and treated combinatorially using the so-called Heffter-Edmonds-Ringel rotation principle. But, to prove this rigorously requires a substantial amount of work. This is the subject of the first three chapters of the present work. Chapter 1 introduces basic graph theoretic concepts. Chapters 2 and 3 contain basic topological results: The Jordan Curve Theorem, the Jordan-Schoenfliess Theorem, and the classification theorem for compact 2-dimensional surfaces, following Thomassen [Th92].
Chapter 2 also treats planar graphs and includes a fundamental result of Koebe [Ko36] and its applications to circle packing representations and extensions of Steinitz' theorem. In Chapter 3 we complete the discussion needed for the purely combinatorial description of graphs on surfaces.
In the last five chapters, graphs on surfaces are formally treated purely combinatorially. Although one may ignore the surface completely, it is nevertheless useful to think of and refer to the surface. Chapter 4 builds on this combinatorial approach and treats basic topological concepts like contractibility of cycles, the genus and the maximum genus of graphs. Chapter 5 is about the edge-width and the face-width of an embedded graph. Graphs of large width are of particular interest in that they share many properties with planar graphs.
Chapter 6 addresses the problem of extending an embedding of a subgraph to an embedding of the whole graph in the same surface. The results about embedding extensions are applied in Section 5.4 where we prove that the list of minimal forbidden subgraphs for the projective plane is finite.
Chapter 7 is devoted to the excluded minor theorem of Robertson and Seymour. A short proof of Thomassen [Th98] with only little reference to surfaces is given. That proof depends on two difficult results of Robertson and Seymour, namely the excluded grid theorem [RS86] and the result that the graphs of bounded tree-width are well-quasi-ordered with respect to the minor relation. An accessible proof of the former was obtained recently by Diestel, Jensen, Gorbunov and Thomassen [DJGT98p] and it is presented in Section 7.1. A simple proof of the latter was recently obtained by Mohar and is presented in Section 7.2.
Coloring problems have always played an important role in the theory of graphs on surfaces. Most of them are mentioned in the monograph of Jensen and Toft [JT95]. Some of the most recent results are surveyed in Chapter 8.
We shall maintain an Internet page where we shall report on any errors and necessary revisions of the text in the book. There we shall also discuss any major progress related to the subject of the book, solutions, partial solutions and generalizations of problems stated in the book, and add links to related sites. A link to the home page of the book will be posted on the following address:
http://www.fmf.uni-lj.si/~moharWe wish to thank Dan Archdeacon and Bruce Richter for their careful reading and many suggestions on parts of the manuscript. Thanks are also due to Mike Albertson, Adrien Douady, Martin Juvan, John Maharry, Neil Robertson, Riste Skrekovski, and Robin Thomas for valuable comments, to Gasper Fijavz for drawings of unavoidable configurations in Appendix B. The figures in Appendix A were produced by the authors using the graph drawing package Pajek, written by Vladimir Batagelj and Andrej Mrvar. Support from the Danish Natural Science Research Council and from the University of Ljubljana is gratefully acknowledged.
Ljubljana, Lyngby
March, 1999