Toroidal Graph

A toroidal graph is a graph with graph genus 1. Equivalently, it is a nonplanar graph that admits a torus graph embedding but no planar graph embedding, and hence has toroidal crossing number 0. Every planar graph also has a torus graph embedding. Some authors therefore use "toroidal graph" inclusively for any graph embeddable on a torus, including planar graphs (Gross and Tucker 1987).

A singlecross graph is necessarily toroidal, since its single crossing can be removed by adding a handle. The converse is false: for example, the complete graphs and are toroidal but have graph crossing numbers 3 and 9, respectively, and so are not singlecross.

A nonplanar graph with a projective plane graph embedding is toroidal iff that embedding has face-width 2 or 3. More generally, its graph genus is , where is the face-width and is the floor function (Fiedler et al. 1995).

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). Families of toroidal graphs include the -crossed prism graphs for integers and cycle complements for (E. Weisstein, May 9, 2023).

The dual graph of a cellular embedding of a toroidal graph in the torus also has a torus graph embedding, but it need not be 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 vertex degree at least three that is not embeddable on , although is embeddable on for every edge . A minor-order obstruction additionally requires to be embeddable on for every graph edge , where is obtained by edge contraction (Myrvold and Woodcock 2018). The complete list of forbidden minors for a torus graph embedding is not known, but thousands of obstructions are known (Neufeld and Myrvold 1997, Chambers 2002, Woodcock 2006, cf. Mohar and Škoda 2020). Chambers (2002) found 239,451 topological obstructions and 16,682 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, pp. 10 and 14) found 250,815 forbidden topological minors and 17,535 forbidden minors, the latter listed in their Table 2. In addition, Gagarin et al. (2009) found four forbidden minors and eleven forbidden topological minors for graphs possessing no graph minor and proved that the lists characterize torus graph embedding.

The following table summarizes forbidden minor obstructions of several types, including with vertex connectivity (Olds 2019). Here, denotes identification of one graph vertex of with one graph vertex of , and denotes a graph join. The graph is obtained by subdividing one graph edge of a complete graph and identifying one graph edge of another complete graph with one of the two edges created by the subdivision.

property	count	forbidden minors	reference
-free	4	, , ,	Gagarin et al. (2009)
	3	, ,	Olds (2019)
	3	, ,	Olds (2019)
	68		Mohar and Skoda (2014)

The numbers of unlabeled toroidal simple 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).

For a connected graph that is a simple graph and toroidal, choose a cellular embedding in the torus. The Poincaré formula relates its vertex count , edge count , and graph face count by

(1)

Every graph face has at least three edge occurrences on its boundary, so

(2)

Combining these formulas gives

(3)

The sum of the vertex degrees is , hence

(4)

where is the minimum vertex degree. Therefore

(5)

so . The edge and degree bounds also hold for disconnected toroidal simple graphs, by applying the bounds to their connected components, since planar connected components also satisfy (West 2000, p. 268; Bartlett 2015).

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

			(6)
			(7)
			(8)

where is obtained from by edge deletion of the edges of . Then a subgraph of is toroidal if it contains a graph subdivision of a Kuratowski graph (i.e., is nonplanar) but does not contain any for , 2, 3.