# Toroidal graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Toroidal_graph
> Markdown URL: https://mediated.wiki/source/Toroidal_graph.md
> Source: https://en.wikipedia.org/wiki/Toroidal_graph
> Source revision: 1317717170
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Graph able to be embedded on a torus

 A [cubic graph](/source/Cubic_graph) with 14 vertices embedded on a [torus](/source/Torus)

The [Heawood graph](/source/Heawood_graph) and associated map embedded in the torus.

In the [mathematical](/source/Mathematical) field of [graph theory](/source/Graph_theory), a **toroidal graph** is a [graph](/source/Graph_(discrete_mathematics)) that can be [embedded](/source/Graph_embedding) on a [torus](/source/Torus). In other words, the graph's [vertices](/source/Vertex_(graph_theory)) and [edges](/source/Edge_(graph_theory)) can be placed on a torus such that no edges intersect except at a vertex that belongs to both.

## Examples

Any graph that can be embedded in a plane can also be embedded in a torus, so every [planar graph](/source/Planar_graph) is also a toroidal graph. A toroidal graph that cannot be embedded in a plane is said to have [genus](/source/Genus_(mathematics)) 1.

The [Heawood graph](/source/Heawood_graph), the [complete graph](/source/Complete_graph) K7 (and hence K5 and K6), the [Petersen graph](/source/Petersen_graph) (and hence the [complete bipartite graph](/source/Complete_bipartite_graph) K3,3, since the Petersen graph contains a subdivision of it), one of the [Blanuša snarks](/source/Blanu%C5%A1a_snarks),[1] and all [Möbius ladders](/source/M%C3%B6bius_ladder) are toroidal. More generally, any graph with [crossing number](/source/Crossing_number_(graph_theory)) 1 is toroidal. Some graphs with greater crossing numbers are also toroidal: the [Möbius–Kantor graph](/source/M%C3%B6bius%E2%80%93Kantor_graph), for example, has crossing number 4 and is toroidal.[2]

## Properties

Any toroidal graph has [chromatic number](/source/Chromatic_number) at most 7.[3] The [complete graph](/source/Complete_graph) K7 provides an example of a toroidal graph with chromatic number 7.[4]

Any [triangle-free](/source/Triangle-free_graph) toroidal graph has chromatic number at most 4.[5]

By a result analogous to [Fáry's theorem](/source/F%C3%A1ry's_theorem), any toroidal graph may be [drawn](/source/Graph_drawing) with straight edges in a rectangle with [periodic boundary conditions](/source/Periodic_boundary_conditions).[6] Furthermore, the analogue of [Tutte's spring theorem](/source/Tutte's_spring_theorem) applies in this case.[7] Toroidal graphs also have [book embeddings](/source/Book_embedding) with at most 7 pages.[8]

## Obstructions

By the [Robertson–Seymour theorem](/source/Robertson%E2%80%93Seymour_theorem), there exists a finite set *H* of minimal non-toroidal graphs, such that a graph is toroidal if and only if it has no [graph minor](/source/Graph_minor) in *H*. That is, *H* forms the set of [forbidden minors](/source/Forbidden_graph_characterization) for the toroidal graphs. The complete set *H* is not known, but it has at least 17,523 graphs. Alternatively, there are at least 250,815 non-toroidal graphs that are minimal in the [topological minor](/source/Topological_minor) ordering. A graph is toroidal if and only if it has none of these graphs as a topological minor.[9]

## Gallery

		- Two isomorphic [Cayley graphs](/source/Cayley_graph) of the [quaternion group](/source/Quaternion_group).

		- [Cayley graph](/source/Cayley_graph) of the [quaternion group](/source/Quaternion_group) embedded in the torus.

		- Video of [Cayley graph](/source/Cayley_graph) of the [quaternion group](/source/Quaternion_group) embedded in the torus.

		- The [Pappus graph](/source/Pappus_graph) and associated map embedded in the torus.

## See also

- [Grünbaum–Nash-Williams conjecture](/source/Gr%C3%BCnbaum%E2%80%93Nash-Williams_conjecture), on Hamiltonian cycles in 4-vertex-connected toroidal graphs

- [Topological graph theory](/source/Topological_graph_theory)

- [Toroidal polyhedron](/source/Toroidal_polyhedron)

## Notes

1. **[^](#cite_ref-FOOTNOTEOrbanićPisanskiRandićServatius2004_1-0)** [Orbanić et al. (2004)](#CITEREFOrbanićPisanskiRandićServatius2004).

1. **[^](#cite_ref-FOOTNOTEMarušičPisanski2000_2-0)** [Marušič & Pisanski (2000)](#CITEREFMarušičPisanski2000).

1. **[^](#cite_ref-FOOTNOTEHeawood1890_3-0)** [Heawood (1890)](#CITEREFHeawood1890).

1. **[^](#cite_ref-FOOTNOTEChartrandZhang2008_4-0)** [Chartrand & Zhang (2008)](#CITEREFChartrandZhang2008).

1. **[^](#cite_ref-FOOTNOTEKronkWhite1972_5-0)** [Kronk & White (1972)](#CITEREFKronkWhite1972).

1. **[^](#cite_ref-FOOTNOTEKocayNeilsonSzypowski2001_6-0)** [Kocay, Neilson & Szypowski (2001)](#CITEREFKocayNeilsonSzypowski2001).

1. **[^](#cite_ref-FOOTNOTEGortlerGotsmanThurston2006_7-0)** [Gortler, Gotsman & Thurston (2006)](#CITEREFGortlerGotsmanThurston2006).

1. **[^](#cite_ref-FOOTNOTEEndo1997_8-0)** [Endo (1997)](#CITEREFEndo1997).

1. **[^](#cite_ref-FOOTNOTEMyrvoldWoodcock2018_9-0)** [Myrvold & Woodcock (2018)](#CITEREFMyrvoldWoodcock2018).

## References

- [Chartrand, Gary](/source/Gary_Theodore_Chartrand); [Zhang, Ping](/source/Ping_Zhang_(graph_theorist)) (2008), *Chromatic graph theory*, CRC Press, [ISBN](/source/ISBN_(identifier)) [978-1-58488-800-0](https://en.wikipedia.org/wiki/Special:BookSources/978-1-58488-800-0).

- Endo, Toshiki (1997), "The pagenumber of toroidal graphs is at most seven", *Discrete Mathematics*, **175** (1–3): 87–96, [doi](/source/Doi_(identifier)):[10.1016/S0012-365X(96)00144-6](https://doi.org/10.1016%2FS0012-365X%2896%2900144-6), [MR](/source/MR_(identifier)) [1475841](https://mathscinet.ams.org/mathscinet-getitem?mr=1475841).

- Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), ["Discrete one-forms on meshes and applications to 3D mesh parameterization"](http://www.cs.jhu.edu/~misha/Fall09/Gortler05.pdf) (PDF), *Computer Aided Geometric Design*, **23** (2): 83–112, [doi](/source/Doi_(identifier)):[10.1016/j.cagd.2005.05.002](https://doi.org/10.1016%2Fj.cagd.2005.05.002), [MR](/source/MR_(identifier)) [2189438](https://mathscinet.ams.org/mathscinet-getitem?mr=2189438), [S2CID](/source/S2CID_(identifier)) [135438](https://api.semanticscholar.org/CorpusID:135438).

- [Heawood, P. J.](/source/Percy_John_Heawood) (1890), "Map-colour theorem", *Quarterly Journal of Pure and Applied Mathematics*, First Series, **24**: 322–339.

- Kocay, W.; Neilson, D.; Szypowski, R. (2001), ["Drawing graphs on the torus"](https://web.archive.org/web/20041224204152/http://bkocay.cs.umanitoba.ca/G%26G/articles/Torus.pdf) (PDF), *Ars Combinatoria*, **59**: 259–277, [MR](/source/MR_(identifier)) [1832459](https://mathscinet.ams.org/mathscinet-getitem?mr=1832459), archived from [the original](http://bkocay.cs.umanitoba.ca/g&g/articles/Torus.pdf) (PDF) on 2004-12-24, retrieved 2018-09-06.

- Kronk, Hudson V.; White, Arthur T. (1972), "A 4-color theorem for toroidal graphs", *[Proceedings of the American Mathematical Society](/source/Proceedings_of_the_American_Mathematical_Society)*, **34** (1), American Mathematical Society: 83–86, [doi](/source/Doi_(identifier)):[10.2307/2037902](https://doi.org/10.2307%2F2037902), [JSTOR](/source/JSTOR_(identifier)) [2037902](https://www.jstor.org/stable/2037902), [MR](/source/MR_(identifier)) [0291019](https://mathscinet.ams.org/mathscinet-getitem?mr=0291019).

- [Marušič, Dragan](/source/Dragan_Maru%C5%A1i%C4%8D); [Pisanski, Tomaž](/source/Toma%C5%BE_Pisanski) (2000), "The remarkable generalized Petersen graph *G*(8,3)", *Math. Slovaca*, **50**: 117–121, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.28.7183](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.7183), [hdl](/source/Hdl_(identifier)):[10338.dmlcz/133137](https://hdl.handle.net/10338.dmlcz%2F133137), [MR](/source/MR_(identifier)) [1763113](https://mathscinet.ams.org/mathscinet-getitem?mr=1763113), [Zbl](/source/Zbl_(identifier)) [0984.05044](https://zbmath.org/?format=complete&q=an:0984.05044).

- [Myrvold, Wendy](/source/Wendy_Myrvold); Woodcock, Jennifer (2018), "A large set of torus obstructions and how they were discovered", *[Electronic Journal of Combinatorics](/source/Electronic_Journal_of_Combinatorics)*, **25** (1): P1.16, [doi](/source/Doi_(identifier)):[10.37236/3797](https://doi.org/10.37236%2F3797)

- Neufeld, Eugene; [Myrvold, Wendy](/source/Wendy_Myrvold) (1997), ["Practical toroidality testing"](https://dl.acm.org/doi/10.5555/314161.314392), *Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms*, Association for Computing Machinery, pp. 574–580, [ISBN](/source/ISBN_(identifier)) [978-0-89871-390-9](https://en.wikipedia.org/wiki/Special:BookSources/978-0-89871-390-9).

- Orbanić, Alen; [Pisanski, Tomaž](/source/Toma%C5%BE_Pisanski); [Randić, Milan](/source/Milan_Randi%C4%87); [Servatius, Brigitte](/source/Brigitte_Servatius) (2004), ["Blanuša double"](http://users.wpi.edu/~bservat/blanusa08.pdf) (PDF), *[Math. Commun.](https://en.wikipedia.org/w/index.php?title=Math._Commun.&action=edit&redlink=1)*, **9** (1): 91–103, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.361.2772](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.361.2772).

---
Adapted from the Wikipedia article [Toroidal graph](https://en.wikipedia.org/wiki/Toroidal_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Toroidal_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.