A torus is the orientable surface that has one handle. Here is a picture of a graph embedded on the torus:
The two green arcs should be identified to make a cylinder, then identify the red arcs to make the torus. A graph G is a topological obstruction for the torus if G has minimum degree at least three, and G does not embed on the torus but for all edges e in G, G-e embeds on the torus. A graph G is a minor order obstruction for the torus if G is a topological obstruction for the torus and for all edges e in G, G contract e embeds on the torus. A torus obstruction G is split-delete minimal if G cannot be obtained from an obstruction that has one less vertex by splitting at some vertex and then deleting some subset of the edges.
This page contains all of the torus obstructions that we have discovered so far. This work is explained in a paper by Wendy Myrvold and Jennifer Woodcock (add reference to ELJC paper when available).
The input format for the torus obstructions is upper triangular adjacency format. Each graph starts with the number of vertices and this is followed by the upper triangle of the adjacency matrix (not including the diagonal elements). Here is an example of a graph and its upper triangular adjacency matrix input format:
There has to be a space after the number of vertices, but
other spaces are optional. The files given here have
one graph per line and no spaces. For example, the above
graph is recorded like this:
5 1010111011
The obstructions:
The numbers of vertices and edges in these obstructions are:
For all of the obstructions:
# Edges : 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 8 Vertices: 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 9 Vertices: 0 2 5 2 9 17 6 2 5 0 0 0 0 0 0 0 0 0 0 10 Vertices: 0 15 9 35 40 190 170 102 76 21 1 0 1 0 0 0 0 0 0 11 Vertices: 5 2 49 87 270 892 1878 1092 501 125 22 4 1 0 0 0 0 0 0 12 Vertices: 1 12 6 201 808 2698 6690 6387 1971 499 98 10 3 1 0 0 0 0 0 13 Vertices: 0 0 12 19 820 4967 12781 16727 7287 1548 301 63 7 0 0 0 0 0 0 14 Vertices: 0 0 0 9 38 2476 15219 24355 16397 4053 930 259 32 1 0 0 0 0 0 15 Vertices: 0 0 0 0 0 33 3646 22402 20957 8474 1948 812 197 10 0 0 0 0 0 16 Vertices: 0 0 0 0 0 0 20 2689 17469 10582 3150 1317 777 68 2 0 0 0 0 17 Vertices: 0 0 0 0 0 0 0 0 837 8099 4154 1131 1073 434 11 0 0 0 0 18 Vertices: 0 0 0 0 0 0 0 0 0 133 2332 1472 526 642 156 1 0 0 0 19 Vertices: 0 0 0 0 0 0 0 0 0 0 0 393 435 294 256 48 0 0 0 20 Vertices: 0 0 0 0 0 0 0 0 0 0 0 0 39 100 164 63 17 0 0 21 Vertices: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 63 12 4 0 22 Vertices: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 22 1 1 23 Vertices: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 24 Vertices: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 8 Vertices: 3 9 Vertices: 48 10 Vertices: 660 11 Vertices: 4928 12 Vertices: 19385 13 Vertices: 44532 14 Vertices: 63769 15 Vertices: 58479 16 Vertices: 36074 17 Vertices: 15739 18 Vertices: 5262 19 Vertices: 1426 20 Vertices: 383 21 Vertices: 95 22 Vertices: 26 23 Vertices: 4 24 Vertices: 2 Number of graphs: 250815
For the minor order obstructions:
# Edges : 18 19 20 21 22 23 24 25 26 27 28 29 30 31 8 Vertices: 0 0 0 0 1 0 1 1 0 0 0 0 0 0 9 Vertices: 0 2 5 2 9 13 6 2 4 0 0 0 0 0 10 Vertices: 0 15 3 18 31 117 90 92 72 17 1 0 1 0 11 Vertices: 5 2 0 46 131 569 998 745 287 45 8 3 1 0 12 Vertices: 1 0 0 52 238 1218 2519 1841 505 91 23 2 1 1 13 Vertices: 0 0 0 5 98 836 1985 1924 512 84 46 2 1 0 14 Vertices: 0 0 0 0 9 68 463 943 251 43 86 1 0 0 15 Vertices: 0 0 0 0 0 0 21 118 45 12 85 0 0 0 16 Vertices: 0 0 0 0 0 0 0 4 3 5 41 0 0 0 17 Vertices: 0 0 0 0 0 0 0 0 0 0 8 0 0 0 18 Vertices: 0 0 0 0 0 0 0 0 0 0 1 0 0 0 8 Vertices: 3 9 Vertices: 43 10 Vertices: 457 11 Vertices: 2840 12 Vertices: 6492 13 Vertices: 5493 14 Vertices: 1864 15 Vertices: 281 16 Vertices: 53 17 Vertices: 8 18 Vertices: 1 Number of graphs: 17535
For the split-delete minimal obstructions:
# Edges : 20 21 22 23 24 25 26 27 28 29 30 31 8 Vertices: 0 0 1 0 1 1 0 0 0 0 0 0 9 Vertices: 2 0 2 3 3 1 4 0 0 0 0 0 10 Vertices: 0 1 0 1 16 40 54 17 1 0 1 0 11 Vertices: 0 0 0 0 4 44 36 15 7 3 1 0 12 Vertices: 0 0 0 0 2 31 41 17 3 1 1 1 13 Vertices: 0 0 0 0 2 6 24 5 3 0 0 0 14 Vertices: 0 0 0 0 0 2 4 0 0 0 0 0 8 Vertices: 3 9 Vertices: 15 10 Vertices: 131 11 Vertices: 110 12 Vertices: 97 13 Vertices: 40 14 Vertices: 6 Number of graphs: 402
If you find any more torus obstructions, please send them to me in upper triangular adjacency format so I can add them to the database.