You are previewing Topics in Topological Graph Theory.
O'Reilly logo
Topics in Topological Graph Theory

Book Description

The use of topological ideas to explore various aspects of graph theory, and vice versa, is a fruitful area of research. There are links with other areas of mathematics, such as design theory and geometry, and increasingly with such areas as computer networks where symmetry is an important feature. Other books cover portions of the material here, but there are no other books with such a wide scope. This book contains fifteen expository chapters written by acknowledged international experts in the field. Their well-written contributions have been carefully edited to enhance readability and to standardize the chapter structure, terminology and notation throughout the book. To help the reader, there is an extensive introductory chapter that covers the basic background material in graph theory and the topology of surfaces. Each chapter concludes with an extensive list of references.

Table of Contents

  1. Cover
  2. Title Page
  3. Copyright Page
  4. Contents
  5. Foreword
  6. Preface
  7. Introduction
    1. 1. Graph Theory
    2. 2. Graphs in the Plane
    3. 3. Surfaces
    4. 4. Graphs on Surfaces
  8. 1 Embedding Graphs on Surfaces
    1. 1. Introduction
    2. 2. Graphs and Surfaces
    3. 3. Embeddings
    4. 4. Rotation Systems
    5. 5. Covering Spaces and Voltage Graphs
    6. 6. Enumeration
    7. 7. Algorithms
    8. 8. Graph Minors
  9. 2 Maximum Genus
    1. 1. Introduction
    2. 2. Characterizations and Complexity
    3. 3. Kuratowski-Type Theorems
    4. 4. Upper-Embeddability
    5. 5. Lower Bounds
  10. 3 Distribution of Embeddings
    1. 1. Introduction
    2. 2. Enumerating Embeddings by Surface Type
    3. 3. Total Embedding Distributions
    4. 4. Congruence Classes
    5. 5. The Unimodality Problem
    6. 6. Average Genus
    7. 7. Stratification of Embeddings
  11. 4 Algorithms and Obstructions for Embeddings
    1. 1. Introduction
    2. 2. Planarity
    3. 3. Outerplanarity and Face Covers
    4. 4. Disc Embeddings and the 2-Path Problem
    5. 5. Graph Minors and Obstructions
    6. 6. Algorithms for Embeddability in General Surfaces
    7. 7. Computing the Genus
  12. 5 Graph Minors: Generalizing Kuratowski’s Theorem
    1. 1. Introduction
    2. 2. Graph Decompositions
    3. 3. Linked Decompositions
    4. 4. Graphs with Bounded Tree-Width
    5. 5. Finding Large Grids
    6. 6. Embedding Large Grids
  13. 6 Colouring Graphs on Surfaces
    1. 1. Introduction
    2. 2. High-End Colouring
    3. 3. A transition from High-End to Low-End Colouring
    4. 4. Colouring Graphs with Few Colours
    5. 5. Girth and Chromatic Number
    6. 6. List-Colouring Graphs
    7. 7. More Colouring Extensions
    8. 8. An Open Problem
  14. 7 Crossing Numbers
    1. 1. Introduction
    2. 2. What is the Crossing Number?
    3. 3. General Bounds
    4. 4. Applications to Geometry
    5. 5. Crossing-Critical Graphs
    6. 6. Other Families of Graphs
    7. 7. Algorithmic Questions
    8. 8. Drawings in Other Surfaces
    9. 9. Conclusion
  15. 8 Representing Graphs and Maps
    1. 1. Introduction
    2. 2. Representations of Graphs
    3. 3. Energy and Optimal Representations
    4. 4. Representations of Maps
    5. 5. Representations of Maps in the Plane
    6. 6. Representations of Incidence Geometries and Related Topics
  16. 9. Enumerating Coverings
    1. 1. Introduction
    2. 2. Graph Coverings
    3. 3. Regular Coverings
    4. 4. Surface Branched Coverings
    5. 5. Regular Surface Branched Coverings
    6. 6. Distribution of Surface Branched Coverings
    7. 7. Further Remarks
  17. 10 Symmetric Maps
    1. 1. Introduction
    2. 2. Representing Maps Algebraically
    3. 3. Regular Maps
    4. 4. Cayley Maps
    5. 5. Regular Cayley Maps
    6. 6. Edge-Transitive Maps
    7. 7. Maps and Mathematics
  18. 11. The Genus of a Group
    1. 1. Introduction
    2. 2. Symmetric Embeddings and Groups Acting on Surfaces
    3. 3. Quotient Embeddings and Voltage Graphs
    4. 4. Inequalities
    5. 5. Groups of Low Genus
    6. 6. Genera of Families of Groups
  19. 12. Embeddings and Geometries
    1. 1. Introduction
    2. 2. Surface Models
    3. 3. Projective Geometries
    4. 4. Affine Geometries
    5. 5. 3-Configurations
    6. 6. Partial Geometries
    7. 7. Regular Embeddings for PG(2, n)
    8. 8. Problems
  20. 13.Embeddings and Designs
    1. 1. Introduction
    2. 2. Steiner Triple Systems and Triangulations
    3. 3. Recursive Constructions
    4. 4. Small Systems
    5. 5. Cyclic Embeddings
    6. 6. Concluding Remarks
  21. 14. Infinite Graphs and Planar Maps
    1. 1. Introduction
    2. 2. Ends
    3. 3. Automorphisms
    4. 4. Connectivities
    5. 5. Growth
    6. 6. Infinite Planar Graphs and Maps
  22. 15 Open Problems
    1. 1. Introduction
    2. 2. Drawings and Crossings
    3. 3. Genus and Obstructions
    4. 4. Cycles and Factors
    5. 5. Colourings and Flows
    6. 6. Local Planarity
    7. 7. Thickness, Book Embeddings and Covering Graphs
    8. 8. Geometrical Topics
    9. 9. Algorithms
    10. 10. Infinite Graphs
  23. Notes on Contributors
  24. Index