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 |
Orientable case 10 |
|
5.4.3 |
About the other orientable cases |
|
5.4.4 |
Nonorientable case 5 |
|
5.4.5 |
About nonorientable cases 11, 8, and 2 |
|
5.4.6 |
Exercises |
6. |
The Genus of a Group |
6.1 |
The genus of abelian groups |
|
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 |