# 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 on the Internet:

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 ConnectivityChapter 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 spacesChapter 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 surfacesChapter 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 graphChapter 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 widthChapter 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 surfacesChapter 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 surfaceChapter 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 cyclesAppendix A
**The minimal forbidden subgraphs for the projective plane**

**
**
Appendix B **The unavoidable configurations in planar triangulations**

**
**Bibliography

##### Revised: marec 15, 2004.