Minor-Minimal Non-Toroidal Graphs

Kuratowski's Theorem gives an excluded topological subgraph characterization of planar graphs. It would be nice to know the collection of graphs whose exclusion characterizes graphs that embed on other surfaces. Because of the large number of such graphs, it is common to use the minor ordering (allowing edge contractions and edge deletions) instead of the topological ordering (allowing edge deletions and smoothing degree two vertices).

The projective plane is the only surface besides the plane for which the minimal non-embeddable graphs are known [A]. There are 103 such topological graphs; 35 of these are minor-minimal.

Problem: Find the minor-minimal non-toroidal graphs.

Henry Glover and Phil Huneke have conjectured that there are over 1000 such topological graphs (or was it 10,000?). Bodendiek and Wagner [BW] have found at least 23 minor minimal graphs and conjecture the complete set may have fewer than 30 members: actually they use a finer order including Y-Delta reductions and a variation, so the numbers are not comparable. All minimal non-toroidal graphs on at most 9 vertices are known. There are 3 on eight vertices and 48 on nine vertices (not counting those which are subdivisions of the graphs on eight vertices). The analysis was done both by hand [HH] and by computer [P].

One approach would be as follows. The orientable genus of projective planar graphs is known by a remarkable theorem of Fiedler, Huneke, Richter and Robertson [FHRR]. A projective minor-minimal nontoroidal graph would be minimal with face-width four. One would first find all such graphs (this may even have been done, you would only need find one such graph and then using an unpublished result of Randby extend to all other graphs using Delta-Wye-Delta exchanges). The remaining minor-minimal non-toroidal graphs would be non-projective-planar. As such, they would have to contain one of the minimal non-projective-planar graphs. One could embed each such graph on the torus and use bridges to analyse why the embedding does not extend.

It is suspected that such a program might be out of the reach of human computations. However, calculations by the proposer reveal that it may be within the reach of computer algorithms. Mohar (personal communication) has a linear-time algorithm for embedding graphs in the torus that could prove quite useful. I believe this algorithm may even have been implemented. I believe that John Pearson (University of Auckland) also has a program to embed graphs on the torus that is implemented and fairly efficient for small graphs.

References:

[A] D. Archdeacon, A Kuratowski theorem for the projective plane, J. Graph Theory 5 (1981) 243-246.

[BW] R. Bodendiek and K. Wagner, On the minimal basis of the spindle-surface, Combinatorics and Graph Theory, Banach Center Publications, 25 PWN-Polish Scientific Publishers, Warsaw (1989).

[FHRR] J. Fiedler, J.P. Huneke, R.B. Richter, and N. Robertson, Computing the orientable genus of projective graphs, J. Graph Theory 20 (1995) 297-308.

[HH] A. Hlavacek and J.P. Huneke, 62 Irreducible 9-vertex graphs for the torus, manuscript (1998)

[P] J. Pearson, personal communication (may be stating the work of others) (1998).

Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.