**Problems in Topological Graph
Theory**

Compiled by Dan Archdeacon

*List Started: August 5, 1995Converted to the web: September 1,
1998Last modified: November 15, 1998*

Dan Archdeacon

Dept. of Math. and Stat.

University of Vermont

Burlington VT 05401-1455 USA

Do you think you've got problems? I know I do. This paper contains an ongoing list of open questions in topological graph theory. If you are interested in adding a problem to this list please contact me at the addresses above. The spirit is inclusive---don't submit a problem you're saving for your graduate student. If it appears here, it's fair game. If you solve one of the problems, know some additional history, or recognize it as misphrased or just a stupid question, please let me know so that I can keep the list up-to-date. I've taken quite a bit of liberty editing the submissions. I apologize for any errors introduced.

Enjoy my problems---I do!

- Classical questions on genus
- Coloring graphs and maps
- Drawings and crossings
- Paths, cycles, and matchings
- Symmetries
- Locally planar embeddings
- Computational complexity
- Book embeddings
- Representing graphs and embeddings
- Random topological graph theory
- Miscellaneous problems
- Solved problems from previous editions

Return to the Main Table of Contents

- The effect of edge deletion on the nonorientable genus
- Minor-minimal non-toroidal graphs
- Nearly triangular imbeddings of complete graphs
- Quadrilateral embeddings of composition graphs
- Edge coloring the n-cube
- The genus sequence of a signed graph
- Trading handles for crossings

Return to the Main Table of Contents

- The earth-moon coloring problem
- Ringel's one-chromatic number of surfaces
- Tutte's nowhere-zero 4- and 5-flow conjectures
- Three edge-coloring orientable triangulations
- Four-coloring all but three vertices of a toroidal graph
- The d-diagonal chromatic number
- Generalizations of Tait coloring cubic graphs
- Vertices of odd degree in a triangulation
- Determining triangulations by their four-colorings
- When are there local colorings?

Return to the Main Table of Contents

- The crossing number of the complete graph
- A combinatorial generalization of drawing the complete graph
- Four questions about drawing the complete graph
- Turan's brickyard problem: the crossing number of K(n,m)
- The crossing number of the cube
- The crossing number of a product of cycles
- The rectilinear crossing number
- The thrackle conjecture
- Is the maximum crossing number hereditary?
- A crossing number hereditary under minors
- Drawing rotations in the plane
- Drawing chords in a disk
- Two problems about drawing graphs in the plane
- Straight-ahead cycles in drawings of Eulerian graphs

Return to the Main Table of Contents

- Longest paths in polyhedral graphs
- The cycle double cover conjecture
- Double covering edges by perfect matchings
- 2-Connected spanning subgraphs of bounded degree

Return to the Main Table of Contents

- Regular maps on nonorientable surfaces
- Automorphism groups of Cayley maps
- Regular Cayley maps that are neither balanced nor antibalanced
- Automorphisms adjacent to the identity
- Planar coverings: the 1-2-infinity conjecture

Return to the Main Table of Contents

- Planar graphs in nonplanar surfaces
- Orientable genus of graphs of bounded nonorientable genus
- Finding separating cycles in embedded graphs
- Interpolation conjectures on separating cycles in embedded graphs
- Spanning trees with small degree
- Finding embeddings of large face width
- LEW embeddings of weighted graphs

Return to the Main Table of Contents

Return to the Main Table of Contents

- The pagenumber of complete bipartite graphs
- The average pagenumber of a permutation
- An unusual way to draw graphs in books

Return to the Main Table of Contents

- Planar graphs with integer length straight edges
- Representing graphs by intersecting line segments
- Representing graphs by spheres in 3-space
- Recognizing and coloring rectangle visibility graphs
- Toroidal triangulations with flat faces

Return to the Main Table of Contents

- The expected number of regions in a random embedding of the complete graph
- Partitioning into complete graphs

Return to the Main Table of Contents

- Outerplanar partitions of planar graphs
- Faces covering the edges of a graph
- Boundary-preserving maps between disks
- Two-dimensional Catalan numbers

Return to the Main Table of Contents

Return to the Main Table of Contents