Description
The use of topological ideas to explore various aspects of graph theory, and vice versa, is a fruitful area of research. There are links with other areas of mathematics, such as design theory and geometry, and increasingly with such areas as computer networks where symmetry is an important feature. Other books cover portions of the material here, but there are no other books with such a wide scope. This book contains fifteen expository chapters written by acknowledged international experts in the field. Their well-written contributions have been carefully edited to enhance readability and to standardize the chapter structure, terminology and notation throughout the book. To help the reader, there is an extensive introductory chapter that covers the basic background material in graph theory and the topology of surfaces. Each chapter concludes with an extensive list of references.
Chapter
1 Embedding graphs on surfaces
5. Covering spaces and voltage graphs
2. Characterizations and complexity
3. Kuratowski-type theorems
3 Distribution of embeddings
2. Enumerating embeddings by surface type
3. Total embedding distributions
5. The unimodality problem
7. Stratification of embeddings
4 Algorithms and obstructions for embeddings
3. Outerplanarity and face covers
4. Disc embeddings and the 2-path problem
5. Graph minors and obstructions
6. Algorithms for embeddability in general surfaces
5 Graph minors: generalizing Kuratowski’s theorem
4. Graphs with bounded tree-width
6 Colouring graphs on surfaces
3. A transition from high-end to low-end colouring
4. Colouring graphs with few colours
5. Girth and chromatic number
7. More colouring extensions
2. What is the crossing number?
4. Applications to geometry
5. Crossing-critical graphs
6. Other families of graphs
8. Drawings in other surfaces
8 Representing graphs and maps
2. Representations of graphs
3. Energy and optimal representations
1-dimensional representations and nodal domains
4. Representations of maps
Representations of maps from graph representations
5. Representations of maps in the plane
6. Representations of incidence geometries and related topics
Representations of incidence geometries
4. Surface branched coverings
5. Regular surface branched coverings
6. Distribution of surface branched coverings
2. Representing maps algebraically
2. Symmetric embeddings and groups acting on surfaces
3. Quotient embeddings and voltage graphs
6. Genera of families of groups
12 Embeddings and geometries
7. Regular embeddings for PG(2, n)
13 Embeddings and designs
2. Steiner triple systems and triangulations
3. Recursive constructions
14 Infinite graphs and planar maps
6. Infinite planar graphs and maps
2. Drawings and crossings
Complete bipartite graphs
Geometrical (linear) crossing number
3. Genus and obstructions
Background on obstructions
The four-colour theorem and its relatives
7. Thickness, book embeddings and covering graphs
Intersecting line segments
Finding LEW-weight functions