Graphs on surfaces.

*(English)*Zbl 0979.05002
Johns Hopkins Studies in the Mathematical Sciences. Baltimore, MD: Johns Hopkins University Press (ISBN 0-8018-6689-8/hbk). xii, 291 p. (2001).

From the authors’ introduction: “Graphs on surfaces form a natural link between discrete and continuous mathematics. They enable us to understand both graphs and surfaces better.” The reviewer adds that they give an exceptionally beautiful body of knowledge. This well-written book offers a thorough development of this area. It would serve as an excellent text for a graduate-level course, and as a valuable source for the practioner.

The first three chapters are devoted to the combinatorial description of embeddings, including discrete proofs of classical results such as the Jordan curve theorem and the classification of surfaces. The book includes a comprehensive treatment of maps that are “locally planar” and their properties. Remaining chapters cover bridges, generalizations of Kuratowski’s theorem, graph minors and excluded subgraph theorems, and chromatic properties of maps.

This text nicely complements existing texts about graphs on surfaces by Ringel, White, Gross and Tucker, and Bonnington and Little.

Contents: (1) Introduction: basic definitions. (2) Planar graphs: Jordan-SchĂ¶nflies theorem, Kuratowski’s theorem, dual graphs, Jordan curve theorem. (3) Surfaces: classification, genus, rotation schemes. (4) Embeddings combinatorially, contractibility of cycles, and the genus problem: the 3-path condition, minimum and maximum genus. (5) Width of embeddings: edge-width, face-width, Whitney’s theorem, surface minors and embedding flexibility. (6) Embedding extensions and obstructions: forbidden minors, bridges. (7) Tree-width and the excluded minor theorem: grid minors and well-quasi-orderings. (8) Colorings of graphs on surfaces: choosability, four-color theorem, girth restrictions.

The first three chapters are devoted to the combinatorial description of embeddings, including discrete proofs of classical results such as the Jordan curve theorem and the classification of surfaces. The book includes a comprehensive treatment of maps that are “locally planar” and their properties. Remaining chapters cover bridges, generalizations of Kuratowski’s theorem, graph minors and excluded subgraph theorems, and chromatic properties of maps.

This text nicely complements existing texts about graphs on surfaces by Ringel, White, Gross and Tucker, and Bonnington and Little.

Contents: (1) Introduction: basic definitions. (2) Planar graphs: Jordan-SchĂ¶nflies theorem, Kuratowski’s theorem, dual graphs, Jordan curve theorem. (3) Surfaces: classification, genus, rotation schemes. (4) Embeddings combinatorially, contractibility of cycles, and the genus problem: the 3-path condition, minimum and maximum genus. (5) Width of embeddings: edge-width, face-width, Whitney’s theorem, surface minors and embedding flexibility. (6) Embedding extensions and obstructions: forbidden minors, bridges. (7) Tree-width and the excluded minor theorem: grid minors and well-quasi-orderings. (8) Colorings of graphs on surfaces: choosability, four-color theorem, girth restrictions.

Reviewer: Dan S.Archdeacon (Burlington)