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
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.
