Cover

Half-title

Title

Copyright

Dedication

Contents

Foreword

Preface

Introduction

1. Graph theory

Graphs

Adjacency and degrees

Isomorphisms and automorphisms

Walks, paths and cycles

Connectedness and distance

Bipartite graphs and trees

Special graphs

Operations

Subgraphs and minors

Connectedness and connectivity

Graph colourings

Directed graphs

2. Graphs in the plane

3. Surfaces

4. Graphs on surfaces

The genus of a graph

The crosscap number of a graph

The chromatic number of a surface

Kuratowski-type theorems

References

1 Embedding graphs on surfaces

1. Introduction

2. Graphs and surfaces

3. Embeddings

Planarity and colouring

4. Rotation systems

5. Covering spaces and voltage graphs

Regular voltages

Lifting embeddings

6. Enumeration

7. Algorithms

8. Graph minors

References

2 Maximum genus

1. Introduction

2. Characterizations and complexity

3. Kuratowski-type theorems

4. Upper-embeddability

5. Lower bounds

References

3 Distribution of embeddings

1. Introduction

2. Enumerating embeddings by surface type

Closed-end ladders

Cobblestone paths

Bouquets

3. Total embedding distributions

4. Congruence classes

5. The unimodality problem

6. Average genus

7. Stratification of embeddings

References

4 Algorithms and obstructions for embeddings

1. Introduction

2. Planarity

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

7. Computing the genus

References

5 Graph minors: generalizing Kuratowski’s theorem

1. Introduction

2. Graph decompositions

3. Linked decompositions

4. Graphs with bounded tree-width

5. Finding large grids

6. Embedding large grids

Acknowledgement

References

6 Colouring graphs on surfaces

1. Introduction

2. High-end colouring

3. A transition from high-end to low-end colouring

4. Colouring graphs with few colours

5. Girth and chromatic number

6. List-colouring graphs

7. More colouring extensions

8. An open problem

Acknowledgement

References

7 Crossing numbers

1. Introduction

2. What is the crossing number?

3. General bounds

4. Applications to geometry

5. Crossing-critical graphs

6. Other families of graphs

7. Algorithmic questions

8. Drawings in other surfaces

9. Conclusion

References

8 Representing graphs and maps

1. Introduction

2. Representations of graphs

3. Energy and optimal representations

The Laplace method

1-dimensional representations and nodal domains

The Tutte method

Iterative methods

4. Representations of maps

Flags and involutions

Representations of maps from graph representations

Operations on maps

5. Representations of maps in the plane

Rotational projection

Fundamental polygons

Universal covers

6. Representations of incidence geometries and related topics

Representations of incidence geometries

Related topics

References

9 Enumerating coverings

1. Introduction

2. Graph coverings

3. Regular coverings

4. Surface branched coverings

5. Regular surface branched coverings

6. Distribution of surface branched coverings

7. Further remarks

References

10 Symmetric maps

1. Introduction

2. Representing maps algebraically

3. Regular maps

4. Cayley maps

5. Regular Cayley maps

6. Edge-transitive maps

7. Maps and mathematics

References

11 The genus of a group

1. Introduction

2. Symmetric embeddings and groups acting on surfaces

3. Quotient embeddings and voltage graphs

4. Inequalities

5. Groups of low genus

6. Genera of families of groups

References

12 Embeddings and geometries

1. Introduction

2. Surface models

3. Projective geometries

4. Affine geometries

5. 3-configurations

6. Partial geometries

7. Regular embeddings for PG(2, n)

8. Problems

References

13 Embeddings and designs

1. Introduction

2. Steiner triple systems and triangulations

3. Recursive constructions

4. Small systems

5. Cyclic embeddings

6. Concluding remarks

Acknowledgements

References

14 Infinite graphs and planar maps

1. Introduction

2. Ends

3. Automorphisms

4. Connectivities

5. Growth

6. Infinite planar graphs and maps

References

15 Open problems

1. Introduction

2. Drawings and crossings

Complete graphs

Complete bipartite graphs

Geometrical (linear) crossing number

Maximum crossing number

3. Genus and obstructions

Finding triangulations

Background on obstructions

The torus

Other surfaces

4. Cycles and factors

Cycle double covers

Matchings

Hamiltonian cycles

Other spanning subgraphs

5. Colourings and flows

The four-colour theorem and its relatives

Flows

6. Local planarity

Colouring problems

Hamiltonian cycles

Separating cycles

7. Thickness, book embeddings and covering graphs

Thickness

Earth–Moon colourings

Book embeddings

Planar covers

8. Geometrical topics

Integer-length edges

Intersecting line segments

Discs and spheres

Intersecting curves

9. Algorithms

Finding the genus

Finding cycles

Finding LEW-weight functions

10. Infinite graphs

Colouring the plane

Geodesics

References

Notes on contributors

Index