TOPICS
Search

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 K_5 and K_7 and complete bipartite graph K_(3,3) (West 2000, p. 267). Families of toroidal graphs include the 2n-crossed prism graphs for n>2 and cycle complements C^__n for n>6 (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 K_7 and Heawood graph, as well as the Dyck graph and Shrikhande graph.

A (topological) obstruction for a surface S is a graph G with minimum degree at least three that is not embeddable on S but for every edge e of G, G-e (G with edge e deleted) is embeddable on S. A minor-order obstruction G has the additional property that for every edge e of G, G·e (G with edge e contracted) is embeddable on S (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 239322 topological obstructions and 16629 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 250815 forbidden topological minorsTopological Minor and 17523 forbidden minors. In addition, Gagarin et al. (2009) found four forbidden minors and eleven forbidden graph expansions for toroidal graphs possessing no K_(3,3) minor and proved that the lists are sufficient.

The following table summarizes forbidden minor obstructions of several types, including with vertex connectivity k (Olds 2019). Here, G·H denotes vertex contraction and G+H denotes a graph join.

propertycountforbdden minorsreference
K_(3,3)-free42K_5, K_5·K_5, G_3, G_4=3C_3+K^__2Gagarin et al. (2009)
kappa=032K_(3,3), 2K_5, K_5 union K_(3,3)Olds (2019)
kappa=13K_(3,3)·K_(3,3), K_5·K_5, K_5·K_(3,3)Olds (2019)
kappa=268Mohar and Skoda (2014)

The numbers of toroidal graphs on n=1, 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 g=1, so the Poincaré formula gives the relationship between vertex count V, edge count E, and face count F as

 V-E+F=0.
(1)

However, a toroidal graph also satisfies

 2E>=3F,
(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 3F. On the other hand, because each edge bounds exactly two faces, its is also exactly 2E (Bartlett 2015). Combining these two formulas gives the inequality

 E/V<=3
(3)

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

If is also true that for a toroidal graph,

 2E>=deltaV,
(4)

where delta 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 deltaV by the definition of minimum vertex degree, but it is also equal to 2E (Bartlett 2015).

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

 0=V-E+F>=2/deltaE-E+2/3E,
(5)

so delta<=6 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

B_1=K_8-K_3
(6)
B_2=K_8-(2K_2 union P_3)
(7)
B_3=K_8-K_(2,3),
(8)

where G-H denotes G minus the edges of H. Then a subgraph G of K_8 is toroidal if it contains a Kuratowski graph (i.e., is nonplanar) but does not contain any B_i for i=1,2,3.


See also

Double-Toroidal Graph, Forbidden Minor, Graph Crossing Number, Graph Genus, Nonplanar Graph, Planar Graph, Pretzel Graph, Toroidal Crossing Number, Torus

Explore with Wolfram|Alpha

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 K_8." Israel J. Math. 11, 452-455, 1972.Gagarin, A.; Myrvold, W.; and Chambers, J. "The Obstructions for Toroidal Graphs with no K_3,3'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.Mohar, B. and Škoda, P. "Obstructions of Connectivity Two for Embedding Graphs Into the Torus." Canad. J. Math. 66, 1327-1357, 2014.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.Olds, T. "Forbidden Graph Minors." 2019. https://www.whitman.edu/Documents/Academics/Mathematics/2019/Olds-Guichard.pdf.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.

Cite this as:

Weisstein, Eric W. "Toroidal Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ToroidalGraph.html

Subject classifications