Toroidal Graph

Every planar graph (i.e., graph with graph genus 0) has an embedding on a torus. In contrast, toroidal graphs are embeddable on the torus, but not in the plane, i.e., they have graph genus 1. Equivalently, a toroidal graph is a nonplanar graph with toroidal crossing number 0, i.e., a nonplanar graph that can be embedded on the surface of a torus with no edge crossings.

A graph with graph genus 2 is called double-toroidal (West 2000, p. 266).

Examples of toroidal graphs include the complete graphs  and  and complete bipartite graph  (West 2000, p. 267).

When it exists, the dual graph of a toroidal graph (on the torus) is also toroidal. Examples of such pairs include the complete graph  and Heawood graph, as well as the Dyck graph and Shrikhande graph.

A (topological) obstruction for a surface  is a graph  with minimum degree at least three that is not embeddable on  but for every edge  of ,  ( with edge  deleted) is embeddable on . A minor-order obstruction  has the additional property that for every edge  of ,  ( with edge  contracted) is embeddable on  (Myrvold and Woodcock 2018). The complete list of forbidden graph minors for toroidal embedding of a graph is not known, but thousands of obstructions are known (Neufeld and Myrvold 1997, Chambers 2002, Woodcock 2007; cf. Mohar and Skoda 2020). Chambers (2002) found  topological obstructions and  minor order obstructions that include those on up to eleven vertices, the 3-regular ones on up to 24 vertices, the disconnected ones and those with a cut-vertex. Myrvold and Woodcock (2018) found  forbidden topological minors and  forbidden minors. In addition, Gagarin et al. (2009) found four forbidden minors and eleven forbidden graph expansions for toroidal graphs possessing no  minor and proved that the lists are sufficient.

The numbers of toroidal graphs on , 2, ... nodes are 0, 0, 0, 0, 1, 14, 222, 5365, ... (OEIS A319114), and the corresponding numbers of connected toroidal graphs are 0, 0, 0, 0, 1, 13, 207, 5128, ... (OEIS A319115; E. Weisstein, Sep. 10, 2018).

A toroidal graph has graph genus , so the Poincaré formula gives the relationship between vertex count , edge count , and face count  as

(1)

However, a toroidal graph also satisfies

(2)

as can be derived by taking the sum over every face of the number of edges in each face. Since there are at least 3 edges in a face, this sum is bounded below by . On the other hand, because each edge bounds exactly two faces, its is also exactly  (Bartlett 2015). Combining these two formulas gives the inequality

(3)

which must hold for a graph to be toroidal (West 2000, p. 268).

If is also true that for a toroidal graph,

(4)

where  is the minimum vertex degree. This can be derived similarly as above by summing the degree of each vertex over all of the vertices. This sum must be greater than  by the definition of minimum vertex degree, but it is also equal to  (Bartlett 2015).

Plugging the above two inequalities into the Poincaré formula then gives

(5)

so  for any toroidal graph (Bartlett 2015).

Duke and Haggard (1972; Harary et al. 1973) gave a criterion for the genus of all graphs on 8 and fewer vertices. Define the double-toroidal graphs

			(6)
			(7)
			(8)

where  denotes  minus the edges of . Then a subgraph  of  is toroidal if it contains a Kuratowski graph (i.e., is nonplanar) but does not contain any  for .

REFERENCES

Bartlett, P. "Lecture 5: Toroidal Graphs." CCS Discrete III, Week 10, UCSB. 2015.

 http://web.math.ucsb.edu/~padraic/ucsb_2014_15/ccs_discrete_s2015/ccs_discrete_s2015_lecture5.pdf.Chambers, J. "Hunting for Torus Obstructions." Master's thesis. Dept. of Computer Science, University of Victoria, 2002.

Duke, R. A.; and Haggard, G. "The Genus of Subgraphs of ." Israel J. Math. 11, 452-455, 1972.

Gagarin, A.; Myrvold, W.; and Chambers, J. "The Obstructions for Toroidal Graphs with no 's." Disc. Math. 309, 3625-3631, 2009.

Harary, F.; Kainen, P. C.; Schwenk, A. J.; and White, A. T. "A Maximal Toroidal Graph Which Is Not a Triangulation." Math. Scand. 33, 108-112, 1973.

Mohar, B. and Škoda, P. "Excluded Minors for the Klein Bottle I. Low Connectivity Case." 1 Feb 2020.

 https://arxiv.org/abs/2002.00258.Myrvold, W. and Woodcock, J. "A Large Set of Torus Obstructions and How They Were Discovered." Electronic J. Comb. 25, P1.16, 2018.

Neufeld, E. and Myrvold, W. "Practical Toroidality Testing." In Proceedings of the Eigth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '97. Society for Industrial and Applied Mathematics, pp. 574-580, 1997.

Riskin, A. "On the Nonembeddability and Crossing Numbers of Some Toroidal Graphs on the Klein Bottle." Disc. Math. 234, 77-88, 2001.

Sloane, N. J. A. Sequences A319114 and A319115 in "The On-Line Encyclopedia of Integer Sequences."Thomassen, C. "Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface." Trans. Amer. Math. Soc. 323, 605-635, 1991.

West, D. B. "Surfaces of Higher Genus." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 266-269, 2000.

Woodcock, J. "A Faster Algorithm for Torus Embedding." Master's thesis. Dept. of Computer Science, University of Victoria, 2007.