Problems in Topological Graph Theory

Go to the Table of Contents

Compiled by Dan Archdeacon

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

E-Mail:

http://www.emba.uvm.edu/~archdeac/problems/dan.archdeacon@uvm.edu

Postal Mail:

Dan Archdeacon
Dept. of Math. and Stat.
University of Vermont
Burlington VT 05401-1455 USA

Abstract

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!

Table of Contents

• 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 Problems

Classical questions on genus

• 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

Coloring graphs and maps

• 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

Drawings and crossings

• 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

Paths, cycles, and matchings

• 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

Symmetries

• Regular maps on nonorientable surfaces
• Automorphism groups of Cayley maps
• Automorphisms adjacent to the identity
• Planar coverings: the 1-2-infinity conjecture

Return to the Main Table of Contents

Locally planar embeddings

• 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

Computational complexity

• Finding the crossing number of a cubic graph
• The approximability of graph minimum genus embeddings

Return to the Main Table of Contents

Book embeddings

• 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

Representating graphs and embeddings

• 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

Random topological graph theory

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

Return to the Main Table of Contents

Miscellaneous problems

• 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

Solved problems from previous editions

• Finding the genus of a cubic graph
• Regular Cayley maps that are neither balanced nor antibalanced

Return to the Main Table of Contents

The End