The Foundations of Topological Graph Theory

This is not a traditional work on topological graph theory. No current graph or voltage graph adorns its pages. Its readers will not compute the genus (orientable or non-orientable) of a single non-planar graph. Their muscles will not flex under the strain of lifting walks from base graphs to derived graphs. What is it, then? It is an attempt to place topological graph theory on a purely combinatorial yet rigorous footing. The vehicle chosen for this purpose is the con cept of a 3-graph, which is a combinatorial generalisation of an imbedding. These properly edge-coloured cubic graphs are used to classify surfaces, to generalise the Jordan curve theorem, and to prove Mac Lane's characterisation of planar graphs. Thus they playa central role in this book, but it is not being suggested that they are necessarily the most effective tool in areas of topological graph theory not dealt with in this volume. Fruitful though 3-graphs have been for our investigations, other jewels must be examined with a different lens. The sole requirement for understanding the logical development in this book is some elementary knowledge of vector spaces over the field Z2 of residue classes modulo 2. Groups are occasionally mentioned, but no expertise in group theory is required. The treatment will be appreciated best, however, by readers acquainted with topology. A modicum of topology is required in order to comprehend much of the motivation we supply for some of the concepts introduced.

This is not a traditional work on topological graph theory. Their muscles will not flex under the strain of lifting walks from base graphs to derived graphs. These properly edge-coloured cubic graphs are used to classify surfaces, to generalise the Jordan curve theorem, and to prove Mac Lane's characterisation of planar graphs.

1 Introduction.- 1.1 Sets.- 1.2 Graphs.- 1.3 Subgraphs.- 1.4 Cocyeles.- 1.5 Forests, trees, circuits, and paths.- 1.6 Some elementary results.- 1.7 Theorems about trees.- 1.8 Spanning trees.- 1.9 Eulerian graphs.- 1.10 Bipartite graphs.- 1.11 Contractions.- 1.12 Menger's theorem and n-connected graphs.- 1.13 2-connected graphs.- 1.14 Blocks.- 1.15 The cycle and cocycle spaces of a graph.- 1.16 Double covers.- 2 Maps.- 2.1 Permutations.- 2.2 Maps.- 2.3 Imbeddings of maps.- 2.4 3-graphs.- 2.5 From maps to gems and back again.- 2.6 Premaps.- 3 Classification of Surfaces.- 3.1 Dipoles.- 3.2 Reduced and unitary 3-graphs.- 3.3 Canonical gems.- 3.4 Planar graphs.- 4 Consistent and Coherent Orientations.- 4.1 Orientations.- 4.2 Pairwise coherently orientable nets.- 4.3 Families of circuits.- 4.4 Rings.- 5 Non-separating Curves in Surfaces.- 5.1 The main results and their topological implications.- 5.2 Permutation pairs.- 5.3 A condition for a b-cycle to separate.- 5.4 Fundamental sets of semicycles.- 6 Mac Lane's Theorem for 3-Graphs.- 6.1 Congruence.- 6.2 Semicycle covers.- 6.3 Boundary covers.- 6.4 Partial congruence.- 6.5 Mac Lane's theorem.- 6.6 Whitney's characterisation.- 7 Kuratowski's Theorem.- 7.1 Corollaries of Mac Lane's theorem.- 7.2 Kuratowski's theorem.- 7.3 Wagner's theorem.- 8 Duality.- 8.1 Duals.- 8.2 Constructing orthogonal graphs.- 8.3 Duality for planar graphs.- 8.4 The zigzag space.- 8.5 The principal edge tripartition for planar graphs.- 8.6 Walks.- 8.7 Principal cycles and principal cocycles.- 8.8 Diagonals.- 8.9 Every planar graph has a diagonal.- 8.10 No non-planar graph has a diagonal.- 9 Rings of Bonds.- 9.1 Chordal graphs.- 9.2 Rings of bonds.- 10 Bridges.- 10.1 Residues and bridges.- 10.2 Tutte's characterisation.- List of Symbols.