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

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 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 minorsTopological Minor 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 following table summarizes forbidden minor obstructions of several types, including with vertex connectivity (Olds 2019). Here, denotes vertex contraction and denotes a graph join.

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

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 .