**Problems in
Topological Graph Theory**

Dan Archdeacon passed away in February 2015. This site contains his compiled problems in topological graph theory as he left it. It has not been updated recently. However we hope that it can still be of use to researchers in the field.

Compiled by Dan Archdeacon

*List Started: August 1995*

*Converted to the web: September 1998*

*Extensive revisions: December 2003*

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, recognize it as phrased incorrectly, or think it’s 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. My original goal was to update the list monthly, however, that has proven too difficult. There is no guarantee that references are up-to-date.

Enjoy my problems---I do!

- Classical questions on genus
- Obstructions to embeddings
- Paths, cycles, and matchings
- Coloring graphs and maps
- List colorings and choosability
- Flows
- Locally planar embeddings
- Crossing numbers
- Drawings
- Representing graphs and embeddings
- Geometric graphs
- Symmetries
- Random topological graph theory
- Book embeddings
- Other problems on planar graphs
- Miscellaneous problems
- Solved problems from previous editions
- Problems under construction

Return to the Main Table of Contents

- The effect of edge deletion on the nonorientable genus
- Rotations determined by edge orderings
- Nearly triangular imbeddings of complete graphs
- The genus of the complete graph minus a Hamiltonian cycle
- Quadrilateral embeddings of composition graphs
- Graphs that quadrangulate both the torus and Klein bottle
- The maximum genus of a signature on the complete graph
- The maximum genus of a simple bipartite graph
- The genus sequence of a signed graph

Return to the Main Table of Contents

- Minor-minimal non-toroidal graphs
- Obstructions for the spindle surface
- Obsttructions for embedding digraphs
- Kuratowski covers

Return to the Main Table of Contents

- The cycle double cover conjecture
- Sabidusi's compatibility conjecture
- (8,4)-directed-cycle covers
- Barnette's conjecture
- Hamilton cycles in toroidal graphs
- Double covering edges by perfect matchings
- Covering cubic graphs with perfect matchings
- Perfect matchings in cubic graphs that have empty intersection
- 2-Connected spanning subgraphs of bounded degree

Return to the Main Table of Contents

- The earth-moon coloring problem
- Three edge-coloring orientable
triangulations
- Uniquely
colorable polyhedra
- Determining triangulations by their four-colorings
- Ringel's one-chromatic number of surfaces
- The d-diagonal chromatic number
- Coloring directed planar graphs
- Acyclic list-coloring planar graphs
- The linear arboricity of planar graphs
- 2-coloring plane triangulations
- Extending colorings of planar graphs
- Four-coloring all but three vertices of a toroidal graph
- Vertices of odd degree in a triangulation
- When are there local colorings?
- Edge coloring the n-cube

Return to the Main Table of Contents

- List edge-colorings
- (a:b)-Choosability
- Defective list colorings
- Defective list colorings of planar graphs
- Extending list-5-colorings of planar graphs
- 3-choosability of planar graphs

Return to the Main Table of Contents

- Tutte's nowhere-zero 3- 4- and 5-flow conjectures
- (2 + epsilon)-flows
- Bouchet's 6-flow conjecture
- Realizing degree sequences with graphs having 3-flows

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

- The crossing number of the complete graph
- A combinatorial generalization of 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 crossing number of dense graphs
- How often must curves touch?
- A crossing number hereditary under minors
- Alternate definitions of the crossing number
- Trading handles for crossings

Return to the Main Table of Contents

- The thrackle conjecture
- Is the maximum crossing number hereditary?
- Straight-ahead cycles in drawings of Eulerian graphs
- Two problems about drawing graphs in the plane
- Four questions about drawing the complete graph
- Drawing chords in a disk
- Drawing rotations in the plane

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

Return to the Main Table of Contents

- The chromatic number of the plane and of space
- The rectilinear crossing number
- The geometric thickness of a graph
- Paths in complete geometric graphs
- Rooted geometric forests with fixed point-sets
- Finding geometric trees with fixed bipartite point-sets
- Geometric graphs with each edge crossing at most three others
- Geometric graphs without three disjoint edges
- Geometric realizations of n-vertex graphs

Return to the Main Table of Contents

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

Return to the Main Table of Contents

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

Return to the Main Table of Contents

Return to the Main Table of Contents

- Packing trees into planar graphs
- Tree-tree triangulations
- Outerplanar partitions of planar graphs
- Cuts in digraphs and Woodall's conjecture
- Combinatorial curvature
- Iterated clique graphs of triangulations
- Boundary-preserving maps between disks
- Which coronas are simple?

Return to the Main Table of Contents

- Colin de Verdiere's mu parameter
- Unacoidable
apex-forest and outer-planar graphs
- Graphs with a K_5 subdivision
- Complete graphs in line graphs
- Faces covering the edges of a graph
- Dimension and outer-planar graphs
- Two-dimensional Catalan numbers
- Antichains in the cycle-continuous order
- Mapping planar graphs onto cycles
- The approximability of graph minimum genus embeddings

Return to the Main Table of Contents

- Toroidal triangulations with flat faces
- The genus of the complete tripartite graph
- Finding the genus of a cubic graph
- Planar graphs in nonplanar surfaces
- An
unusual way to draw graphs in books
- Regular Cayley maps that are neither balanced nor antibalanced

Return to the Main Table of Contents

Return to the Main Table of Contents