Topological Graph Theory

1. Introduction 1.1 Representation of Graphs 1.1.1 Drawings 1.1.2 Incidence Matrix 1.1.3 Euler's theorem on valence sum 1.1.4 Adjacency Matrix 1.1.5 Directions 1.1.6 Graphs, maps, isomorphisms 1.1.7 Automorphisms 1.1.8 Exercises 1.2 Some important classes of graphs 1.2.1 Walks, paths, and cycles; connectedness 1.2.2 Trees 1.2.3 Complete graphs 1.2.4 Cayley graphs 1.2.5 Bipartite graphs 1.2.6 Bouquets of Circles 1.2.7 Exercises 1.3 New graphs from old 1.3.1 Subgraphs 1.3.2 Topological representations, subdivisions, graph homeomorphisms 1.3.3 Cartesian products 1.3.4 Edge-complements 1.3.5 Suspensions 1.3.6 Amalgamations 1.3.7 Regular quotients 1.3.8 Regular coverings 1.3.9 Exercises 1.4 Surfaces and imbeddings 1.4.1 Orientable surfaces 1.4.2 Nonorientable surfaces 1.4.3 Imbeddings 1.4.4 Euler's equation for the sphere 1.4.5 Kuratowski's graphs 1.4.6 Genus of surfaces and graphs 1.4.7 The torus 1.4.8 Duality 1.4.9 Exercises 1.5 More graph-theoretic background 1.5.1 Traversability 1.5.2 Factors 1.5.3 Distance, neighborhoods 1.5.4 Graphs colorings and map colorings 1.5.5 Edge operations 1.5.6 Algorithms 1.5.7 Connectivity 1.5.8 Exercises 1.6 Planarity 1.6.1 A nearly complete sketch of the proof 1.6.2 Connectivity and region boundaries 1.6.3 Edge contraction and connectivity 1.6.4 Planarity theorems for 3-connected graphs 1.6.5 Graphs that are not 3-connected 1.6.6 Algorithms 1.6.7 Kuratowski graphs for higher genus 1.6.8 Other planarity criteria 1.6.9 Exercises 2. Voltage Graphs and Covering Spaces 2.1 Ordinary voltages 2.1.1 Drawings of voltage graphs 2.1.2 Fibers and the natural projection 2.1.3 The net voltage on a walk 2.1.4 Unique walk lifting 2.1.5 Preimages of cycles 2.1.6 Exercises 2.2 Which graphs are derivable with ordinary voltages? 2.2.1 The natural action of the voltage group 2.2.2 Fixed-point free automorphisms 2.2.3 Cayley graphs revisited 2.2.4 Automorphism groups of graphs 2.2.5 Exercises 2.3 Irregular covering graphs 2.3.1 Schreier graphs 2.3.2 Relative voltages 2.3.3 Combinatorial coverings 2.3.4 Most regular graphs are Schreier graphs 2.3.5 Exercises 2.4 Permutation voltage graphs 2.4.1 Constructing covering spaces with permutations 2.4.2 Preimages of walks and cycles 2.4.3 Which graphs are derivable by permutation voltages? 2.4.4 Identifying relative voltages with permutation voltages 2.4.5 Exercises 2.5 Subgroups of the voltage group 2.5.1 The fundamental semigroup of closed walks 2.5.2 Counting components of ordinary derived graphs 2.5.3 The fundamental group of a graph 2.5.4 Contracting derived graphs onto Cayley graphs 2.5.5 Exercises 3. Surfaces and Graph Imbeddings 3.1 Surfaces and simplicial complexes 3.1.1 Geometric simplicial complexes 3.1.2 Abstract simplicial complexes 3.1.3 Triangulations 3.1.4 Cellular imbeddings 3.1.5 Representing surfaces by polygons 3.1.6 Pseudosurfaces and block designs 3.1.7 Orientations 3.1.8 Stars, links, and local properties 3.1.9 Exercises 3.2 Band Decompositions and graph imbeddings 3.2.1 Band decomposition for surfaces 3.2.2 Orientability 3.2.3 Rotation systems 3.2.4 Pure rotation systems and orientable surfaces 3.2.5 Drawings of rotation systems 3.2.6 Tracing faces 3.2.7 Duality 3.2.8 Which 2-complexes are planar? 3.2.9 Exercises 3.3 The classification of surfaces 3.3.1 Euler characteristic relative to an imbedded graph 3.3.2 Invariance of Euler characteristic 3.3.3 Edge-deletion surgery and edge sliding 3.3.4 Completeness of the set of orientable models 3.3.5 Completeness of the set of nonorientable models 3.3.6 Exercises 3.4 The imbedding distribution of a graph 3.4.1 The absence of gaps in the genus range 3.4.2 The absence of gaps in the crosscap range 3.4.3 A genus-related upper bound on the crosscap number 3.4.4 The genus and crosscap number of the complete graph K subscript 7 3.4.5 Some graphs of crosscap number 1 but arbitrarily large genus 3.4.6 Maximum genus 3.4.7 Distribution of genus and face sizes 3.4.8 Exercises 3.5 Algorithms and formulas for minimum imbeddings 3.5.1 Rotation-system algorithms 3.5.2 Genus of an amalgamation 3.5.3 Crosscap number of an amalgamation 3.5.4 The White-Pisanski imbedding of a cartesian product 3.5.5 Genus and crosscap number of cartesian products 3.5.6 Exercises 4. Imbedded voltage graphs and current graphs 4.1 The derived imbedding 4.1.1 Lifting rotation systems 4.1.2 Lifting faces 4.1.3 The Kirchhoff Voltage Law 4.1.4 Imbedded permutation voltage graphs 4.1.5 Orientability 4.1.6 An orientability test for derived surfaces 4.1.7 Exercises 4.2 Branched coverings of surfaces 4.2.1 Riemann surfaces 4.2.2 Extension of the natural covering projection 4.2.3 Which branch coverings come from voltage graphs? 4.2.4 The Riemann-Hurwitz equation 4.2.5 Alexander's theorem 4.2.6 Exercises 4.3 Regular branched coverings and group actions 4.3.1 Groups acting on surfaces 4.3.2 Graph automorphisms and rotation systems 4.3.3 Regular branched coverings and ordinary imbedded voltage graphs 4.3.4 Which regular branched coverings come from voltage graphs? 4.3.5 Applications to group actions on the surface S subscript 2 4.3.6 Exercises 4.4 Current graphs 4.4.1 Ringel's generating rows for Heffter's schemes 4.4.2 Gustin's combinatorial current graphs 4.4.3 Orientable topological current graphs 4.4.4 Faces of the derived graph 4.4.5 Nonorientable current graphs 4.4.6 Exercises 4.5 Voltage-current duality 4.5.1 Dual directions 4.5.2 The voltage graph dual to a current graph 4.5.3 The dual derived graph 4.5.4 The genus of the complete bipartite graph K (subscript m, n) 4.5.5 Exercises 5. Map colorings 5.1 The Heawood upper bound 5.1.1 Average valence 5.1.2 Chromatically critical graphs 5.1.3 The five-color theorem 5.1.4 The complete-graph imbedding problem 5.1.5 Triangulations of surfaces by complete graphs 5.1.6 Exercises 5.2 Quotients of complete-graph imbeddings and some variations 5.2.1 A base imbedding for orientable case 7 5.2.2 Using a coil to assign voltages 5.2.3 A current-graph perspective on case 7 5.2.4 Orientable case 4: doubling 1-factors 5.2.5 About orientable cases 3 and 0 5.2.6 Exercises 5.3 The regular nonorientable cases 5.3.1 Some additional tactics 5.3.2 Nonorientable current graphs 5.3.3 Nonorientable cases 3 and 7 5.3.4 Nonorientable case 0 5.3.5 Nonorientable case 4 5.3.6 About nonorientable cases 1, 6, 9, and 10 5.3.7 Exercises 5.4 Additional adjacencis for irregular cases 5.4.1 Orientable case 5 5.4.2 Orie 6.1.1 Recovering a Cayley graph from any of its quotients 6.1.2 A lower bound for the genus of most abelian groups 6.1.3 Constructing quadrilateral imbeddings for most abelian groups 6.1.4 Exercises 6.2 The symmetric genus 6.2.1 Rotation systems and symmetry 6.2.2 Reflections 6.2.3 Quotient group actions on quotient surfaces 6.2.4 Alternative Cayley graphs revisited 6.2.5 Group actions and imbeddings 6.2.6 Are genus and symmetric genus the same? 6.2.7 Euclidean space groups and the torus 6.2.8 Triangle groups 6.2.9 Exercises 6.3 Groups of small symmetric genus 6.3.1 The Riemann-Hurwitz equation revisited 6.3.2 Strong symmetric genus 0 6.3.3 Symmetric genus 1 6.3.4 The geometry and algebra of groups of symmetric genus 1 6.3.5 Hurwitz's theorem 6.3.6 Exercises 6.4 Groups of small genus 6.4.1 An example 6.4.2 A face-size inequality 6.4.3 Statement of main theorem 6.4.4 Proof of theorem 6.4.2: valence d = 4 6.4.5 Proof of theorem 6.4.2: valence d = 3 6.4.6 Remarks about Theorem 6.4.2 6.4.7 Exercises References Bibliography Supplementary Bibliography Table of Notations Subject Index