Graphs on Surfaces

Contents:
Chapter 1. Introduction
Basic Definition
Trees and bipartite graphs
Blocks
ConnectivityChapter 2. Planar Graphs
Planar graphs and the Jordan Curve Theorem
The Jordan-Schonflies Theorem
The Theorem of Kuratowski
Characterizations of planar graphs
3-connected planar graphs
Dual graphs
Planarity algorithms
Circle packing representations
The Riemann Mapping Theorem
The Jordan Curve Theorem and Kuratowski's Theorem in general topological spacesChapter 3. Surfaces
Classification of surfacesRotation systemsEmbedding schemesThe genus of a graphClassification of noncompact surfacesChapter 4. Embeddings Combinatorially, Contractibility, of Cycles, and the Genus Problem
Embeddings combinatoriallyCycles of embedded graphsThe 3-path-conditionThe genus of a graphThe maximum genus of a graphChapter 5. The Width of Embeddings
Edge-width
2-flippings and uniqueness of LEW-embeddings
Triangulations
Minimal triangulations of a given edge-width
Face-width
Minimal embeddings of a given face-width
Embeddings of planar graphs
The genus of a graph with a given nonorientable embedding
Face-width and surface minors
Face-width and embedding flexibility
Combinatorial properties of embedded graphs of large widthChapter 6. Embedding Extensions and Obstructions
Forbidden subgraphs and forbidden minors
Bridges
Obstruction in a bridge
2-restricted embedding extensions
The forbidden subgraphs for the projective plane
The minimal forbidden subgraphs for general surfacesChapter 7. Tree-Width and the Excluded Minor Theorem
Tree-width and the excluded grid theoremThe excluded minor theorem for any fixed surfaceChapter 8. Colorings of Graphs on Surfaces
Planar graphs are 5-choosable
The Four Color Theorem
Color critical graphs and the Heawood formula
Coloring in a few colors
Graphs without short cycles
Appendix A. The minmal forbidden subgraphs for the projective plane
Appendix B. The unavoidable configurations in planar triangulations
Bibliography
Index