Graphs on Surfaces

Bojan Mohar and Carsten Thomassen

Johns Hopkins University Press

The book Graphs on Surfaces has appeared in July 2001, published by the Johns Hopkins University Press.
The book can be ordered online:

Some open problems from the book and progres towards their solution.

Errata

Table of contents

Preface

Chapter 1   Introduction

 1.1   Basic definitions
1.2   Trees and bipartite graphs
1.3   Blocks
1.4   Connectivity

Chapter 2   Planar graphs

 2.1   Planar graphs and the Jordan Curve Theorem
2.2   The Jordan-Schonflies Theorem
2.3   The Theorem of Kuratowski
2.4   Characterizations of planar graphs
2.5   3-connected planar graphs
2.6   Dual graphs
2.7   Planarity algorithms
2.8   Circle packing representations
2.9   The Riemann Mapping Theorem
2.10   The Jordan Curve Theorem and Kuratowski's Theorem in general topological spaces

Chapter 3   Surfaces

3.1   Classification of surfaces
3.2   Rotation systems
3.3   Embedding schemes
3.4   The genus of a graph
3.5   Classification of noncompact surfaces

Chapter 4   Embeddings combinatorially, contractibility of cycles, and the genus problem

 4.1   Embeddings combinatorially
4.2   Cycles of embedded graphs
4.3   The 3-path-condition
4.4   The genus of a graph
4.5   The maximum genus of a graph

Chapter 5   The width of embeddings

 5.1   Edge-width
5.2   2-flippings and uniqueness of LEW-embeddings
5.3   Triangulations
5.4   Minimal triangulations of a given edge-width
5.5   Face-width
5.6   Minimal embeddings of a given face-width
5.7   Embeddings of planar graphs
5.8   The genus of a graph with a given orientable embedding
5.9   Face-width and surface minors
5.10   Face-width and embedding flexibility
5.11   Combinatorial properties of embedded graphs of large width

Chapter 6   Embedding extensions and obstructions

 6.1   Forbidden subgraphs and forbidden minors
6.2   Bridges
6.3   Obstructions in a bridge
6.4   2-restricted embedding extensions
6.5   The forbidden subgraphs for the projective plane
6.6   The minimal forbidden subgraphs for general surfaces

Chapter 7   Tree-width and the excluded minor theorem

 7.1   Tree-width and the excluded grid theorem
7.2   Minimal obstructions of bounded tree-width
7.3   The excluded minor theorem for any fixed surface

Chapter 8   Colorings of graphs on surfaces

 8.1   Planar graphs are 5-colorable
8.2   The Four Color Theorem
8.3   Color critical graphs and the Heawood formula
8.4   Coloring in few colors
8.5   Graphs without short cycles

Appendix A   The minimal forbidden subgraphs for the projective plane

Appendix B   The unavoidable configurations in planar triangulations

Bibliography
Revised: januar 04, 2021.