Topological Graph Theory - Class Notes
From Graphs on Surfaces Bojan Mohar and Carsten Thomassen, (Johns Hopkins University Press, 2001)
ETSU does not have a formal class on Topological Graph Theory. However, we do have a Graph Theory sequence. Notes are online for
Graph Theory 1 (MATH 5340) and Graph Theory 2 (MATH 5450).
The catalog description for Graph Theory 1 is: "Topics include special classes of graphs, distance in graphs, graphical parameters, connectivity, Eulerian graphs, hamiltonian graphs, networks, and extremal graph theory. Theory and proof techniques will be emphasized."
The catalog description for Graph Theory 2 is: "Analyze topics in planar graphs, the Four Color Theorem, vertex/edge colorings, random graphs, and contemporary research topics in graph theory."
Copies of the classnotes are on the internet in PDF format as given below. The notes and supplements may contain hyperlinks to posted webpages; the links appear in red fonts. The "Proofs of Theorems" files were prepared in Beamer. The "Printout of Proofs" are printable PDF files of the Beamer slides without the pauses. These notes have not been classroom tested and may have typographical errors. A webpage for the book prepared by Bojan Mohar is available and includes information on open problems (listed as "Revised October 16, 2009") and a a brief Errata page.
- Chapter 1. Introduction.
- Chapter 2. Planar Graphs.
- Chapter 3. Surfaces.
- Chapter 4. Embeddings Combinatorially, Contractibility of Cycles, and the Genus Problem.
- Chapter 5. The Width of Embeddings.
- Chapter 6. Embedding Extensions and Obstructions.
- Chapter 7. Tree-Width and the Excluded Minor Theorem.
- Chapter 8. Colorings of Graphs on Surfaces.
- Appendix A. The Mimimal Forbidden Subgraphs for the Projective Plane.
- Appendix B. The Unavoidable Configurations in Planar Triangulations.
1. Introduction.
2. Planar Graphs.
- 2.1. Planar Graphs and the Jordan Curve Theorem.
- 2.2. The Jordan-Schönflies Theorem.
- 2.3. The Theorem of Kuratowksi.
- 2.4. Characterizations of Planar Graphs.
- 2.5. 3-Connected Planar Graphs.
- 2.6. Dual Graphs.
- 2.7. Planarity Algorithms.
- 2.8. Circle Packing Representations.
- 2.9. The Riemann Mapping Theorem.
- 2.10. The Jordan Curve Theorem and Kuratowski's Theorem in General Topological Spaces.
3. Surfaces.
- 3.1. Classification of Surfaces.
- 3.2. Rotation Systems.
- 3.3. Embedding Schemes.
- 3.4. The Genus of a Graph.
- 3.5. Classification of Noncompact Surfaces.
4. Embeddings Combinatorially, Contractibility of Cycles, and the Genus Problem.
- 4.1. Embedding Combinatorially.
- 4.2. Cycles of Embedded Graphs.
- 4.3. The 3-Path Condition.
- 4.4. The Genus of a Graph.
- 4.5. The Maximum Genus of a Graphs.
5. The Width of Embeddings.
- 5.1. Edge-Width.
- 5.2. 2-Flippings and Uniqueness of LEW-Embeddings.
- 5.3. Triangluations.
- 5.4. Minimal Triangulations of a Given Edge-Width.
- 5.5. Face-Width.
- 5.6. Minimal Enbeddings of a Given Face-Width.
- 5.7. Embeddings of Planar Graphs.
- 5.8. The Genus of a Graph with a Given Nonorientable Embedding.
- 5.9. Face-Width and Surface Minors.
- 5.10. Face-Width and Embedding Flexibility.
- 5.11. Combinatorial Properties of Embedded Graphs of Large Width.
6. Embedding Extensions and Obstructions.
- 6.1. Forbidden Subgraphs and Forbidden Minors.
- 6.2. Bridges.
- 6.3. Obstructions in a Bridge.
- 6.4. 2-Restricted Embeddings Extensions.
- 6.5. The Forbidden Subgraphs for the Projective Plane.
- 6.6. The Minimal Forbidden Subgraphs for General Surfaces.
7. Tree-Width and the Excluded Minor Theorem.
- 7.1. Tree-Width and the Excluded Grid Theorem.
- 7.2. Minimal Obstructions of Bounded Tree-Width.
- 7.3. The Excluded Minor Theorem for any Fixed Surface.
8. Colorings of Graphs on Surfaces.
- 8.1. Planar Graphs are 5-Choosable.
- 8.2. The Four Color Theorem.
- 8.3. Color Critical Graphs and the Heawood Formula.
- 8.4. Coloring in Few Colors.
- 8.5. Graphs without Short Cycles.
- 8.6. Positive Semidefinite Matrices.
Appendix A. The Mimimal Forbidden Subgraphs for the Projective Plane.
Appendix B. The Unavoidable Configurations in Planar Triangulations.
Return to Bob Gardner's home page
|