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 
Edgecomplements 

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 graphtheoretic 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 3connected graphs 

1.6.5 
Graphs that are not 3connected 

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 
Fixedpoint 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 2complexes 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 
Edgedeletion 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 genusrelated 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 
Rotationsystem algorithms 

3.5.2 
Genus of an amalgamation 

3.5.3 
Crosscap number of an amalgamation 

3.5.4 
The WhitePisanski 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 RiemannHurwitz 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 
Voltagecurrent 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 fivecolor theorem 

5.1.4 
The completegraph imbedding problem 

5.1.5 
Triangulations of surfaces by complete graphs 

5.1.6 
Exercises 
5.2 
Quotients of completegraph 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 currentgraph perspective on case 7 

5.2.4 
Orientable case 4: doubling 1factors 

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 RiemannHurwitz 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 facesize 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 