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