Topics in Topological Graph Theory

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.

Foreword	p. xv
Preface	p. xvii
Introduction	p. 1
Graph theory	p. 1
Graphs in the plane	p. 10
Surfaces	p. 12
Graphs on surfaces	p. 14
Embedding graphs on surfaces	p. 18
Introduction	p. 18
Graphs and surfaces	p. 19
Embeddings	p. 20
Rotation systems	p. 23
Covering spaces and voltage graphs	p. 26
Enumeration	p. 29
Algorithms	p. 30
Graph minors	p. 31
Maximum genus	p. 34
Introduction	p. 34
Characterizations and complexity	p. 36
Kuratowski-type theorems	p. 38
Upper-embeddability	p. 39
Lower bounds	p. 40
Distribution of embeddings	p. 45
Introduction	p. 45
Enumerating embeddings by surface type	p. 48
Total embedding distributions	p. 51
Congruence classes	p. 53
The unimodality problem	p. 55
Average genus	p. 56
Stratification of embeddings	p. 59
Algorithms and obstructions for embeddings	p. 62
Introduction	p. 62
Planarity	p. 64
Outerplanarity and face covers	p. 66
Disc embeddings and the 2-path problem	p. 68
Graph minors and obstructions	p. 69
Algorithms for embeddability in general surfaces	p. 73
Computing the genus	p. 75
Graph minors: generalizing Kuratowski's theorem	p. 81
Introduction	p. 81
Graph decompositions	p. 84
Linked decompositions	p. 88
Graphs with bounded tree-width	p. 94
Finding large grids	p. 99
Embedding large grids	p. 107
Colouring graphs on surfaces	p. 111
Introduction	p. 111
High-end colouring	p. 113
A transition from high-end to low-end colouring	p. 116
Colouring graphs with few colours	p. 119
Girth and chromatic number	p. 124
List-colouring graphs	p. 125
More colouring extensions	p. 127
An open problem	p. 129
Crossing numbers	p. 133
Introduction	p. 133
What is the crossing number?	p. 135
General bounds	p. 137
Applications to geometry	p. 139
Crossing-critical graphs	p. 139
Other families of graphs	p. 143
Algorithmic questions	p. 144
Drawings in other surfaces	p. 146
Conclusion	p. 147
Representing graphs and maps	p. 151
Introduction	p. 151
Representations of graphs	p. 152
Energy and optimal representations	p. 155
Representations of maps	p. 163
Representations of maps in the plane	p. 170
Representations of incidence geometries and related topics	p. 174
Enumerating coverings	p. 181
Introduction	p. 181
Graph coverings	p. 183
Regular coverings	p. 185
Surface branched coverings	p. 190
Regular surface branched coverings	p. 193
Distribution of surface branched coverings	p. 195
Further remarks	p. 196
Symmetric maps	p. 199
Introduction	p. 199
Representing maps algebraically	p. 200
Regular maps	p. 205
Cayley maps	p. 210
Regular Cayley maps	p. 212
Edge-transitive maps	p. 218
Maps and mathematics	p. 221
The genus of a group	p. 225
Introduction	p. 225
Symmetric embeddings and groups acting on surfaces	p. 226
Quotient embeddings and voltage graphs	p. 228
Inequalities	p. 232
Groups of low genus	p. 235
Genera of families of groups	p. 239
Embeddings and geometries	p. 245
Introduction	p. 245
Surface models	p. 248
Projective geometries	p. 250
Affine geometries	p. 253
3-configurations	p. 256
Partial geometries	p. 260
Regular embeddings for PG(2,n)	p. 264
Problems	p. 265
Embeddings and designs	p. 268
Introduction	p. 268
Steiner triple systems and triangulations	p. 270
Recursive constructions	p. 273
Small systems	p. 278
Cyclic embeddings	p. 280
Concluding remarks	p. 284
Infinite graphs and planar maps	p. 289
Introduction	p. 289
Ends	p. 290
Automorphisms	p. 293
Connectivities	p. 295
Growth	p. 300
Infinite planar graphs and maps	p. 303
Open problems	p. 313
Introduction	p. 313
Drawings and crossings	p. 314
Genus and obstructions	p. 317
Cycles and factors	p. 320
Colourings and flows	p. 322
Local planarity	p. 324
Thickness, book embeddings and-covering graphs	p. 325
Geometrical topics	p. 328
Algorithms	p. 330
Infinite graphs	p. 332
Notes on contributors	p. 337
Index	p. 341
Table of Contents provided by Ingram. All Rights Reserved.

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Topics in Topological Graph Theory

Summary

Table of Contents

Supplemental Materials