Toroidal graph

Any graph that can be embedded in a plane can also be embedded in a torus, so every planar graph is also a toroidal graph. A toroidal graph that cannot be embedded in a plane is said to have genus 1.

The Heawood graph, the complete graph K₇ (and hence K₅ and K₆), the Petersen graph (and hence the complete bipartite graph K_3,3, since the Petersen graph contains a subdivision of it), one of the Blanuša snarks,{{sfnp|Orbanić|Pisanski|Randić|Servatius|2004}} and all Möbius ladders are toroidal. More generally, any graph with crossing number 1 is toroidal. Some graphs with greater crossing numbers are also toroidal: the Möbius–Kantor graph, for example, has crossing number 4 and is toroidal.{{sfnp|Marušič|Pisanski|2000}}

Any toroidal graph has chromatic number at most 7.{{sfnp|Heawood|1890}} The complete graph K₇ provides an example of a toroidal graph with chromatic number 7.{{sfnp|Chartrand|Zhang|2008}}

Any triangle-free toroidal graph has chromatic number at most 4.{{sfnp|Kronk|White|1972}}

By a result analogous to Fáry's theorem, any toroidal graph may be drawn with straight edges in a rectangle with periodic boundary conditions.{{sfnp|Kocay|Neilson|Szypowski|2001}} Furthermore, the analogue of Tutte's spring theorem applies in this case.{{sfnp|Gortler|Gotsman|Thurston|2006}}

Toroidal graphs also have book embeddings with at most 7 pages.{{sfnp|Endo|1997}}

By the Robertson–Seymour 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 in H.

That is, H forms the set of forbidden minors 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 ordering.

A graph is toroidal if and only if it has none of these graphs as a topological minor.{{sfnp|Myrvold|Woodcock|2018}}

File:Cayley graphs of the quaternion group.png|Two isomorphic Cayley graphs of the quaternion group.

File:Cayley graph of quaternion group on torus.png|Cayley graph of the quaternion group embedded in the torus.

File:Quaternion group.webm|Video of Cayley graph of the quaternion group embedded in the torus.

File:Pappus-graph-on-torus.png|The Pappus graph and associated map embedded in the torus.

• Planar graph
• Topological graph theory
• Császár polyhedron

{{reflist}}

• {{citation

| last1 = Chartrand | first1 = Gary | author1-link = Gary Theodore Chartrand

| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)

| isbn = 978-1-58488-800-0

| publisher = CRC Press

| title = Chromatic graph theory

| year = 2008}}.

• {{citation

| last = Endo | first = Toshiki

| doi = 10.1016/S0012-365X(96)00144-6

| mr = 1475841

| issue = 1–3

| journal = Discrete Mathematics

| pages = 87–96

| title = The pagenumber of toroidal graphs is at most seven

| volume = 175

| year = 1997| doi-access =

}}.

• {{citation

| last1 = Gortler | first1 = Steven J.

| last2 = Gotsman | first2 = Craig

| last3 = Thurston | first3 = Dylan

| doi = 10.1016/j.cagd.2005.05.002

| mr = 2189438

| issue = 2

| journal = Computer Aided Geometric Design

| pages = 83–112

| title = Discrete one-forms on meshes and applications to 3D mesh parameterization

| volume = 23

| year = 2006| s2cid = 135438

| url = http://www.cs.jhu.edu/~misha/Fall09/Gortler05.pdf

}}.

• {{citation

| last = Heawood | first = P. J. | author-link = Percy John Heawood

| journal = Quarterly Journal of Pure and Applied Mathematics |series=First Series

| pages = 322–339

| title = Map-colour theorem

| volume = 24

| year = 1890}}.

• {{citation

|last1 = Kocay

|first1 = W.

|last2 = Neilson

|first2 = D.

|last3 = Szypowski

|first3 = R.

|mr = 1832459

|journal = Ars Combinatoria

|pages = 259–277

|title = Drawing graphs on the torus

|url = http://bkocay.cs.umanitoba.ca/g&g/articles/Torus.pdf

|volume = 59

|year = 2001

|access-date = 2018-09-06

|archive-url = https://web.archive.org/web/20041224204152/http://bkocay.cs.umanitoba.ca/G%26G/articles/Torus.pdf

|archive-date = 2004-12-24

|url-status = dead

}}.

• {{citation

| last1 = Kronk | first1 = Hudson V.

| last2 = White | first2 = Arthur T.

| doi = 10.2307/2037902

| mr = 0291019

| issue = 1

| journal = Proceedings of the American Mathematical Society

| pages = 83–86

| publisher = American Mathematical Society

| title = A 4-color theorem for toroidal graphs

| volume = 34

| year = 1972

| jstor = 2037902}}.

• {{citation

|last1 = Marušič

|first1 = Dragan

|author1-link = Dragan Marušič

|last2 = Pisanski

|first2 = Tomaž

|author2-link = Tomaž Pisanski

|journal = Math. Slovaca

|pages = 117–121

|title = The remarkable generalized Petersen graph G(8,3)

|hdl = 10338.dmlcz/133137 |citeseerx=10.1.1.28.7183 |mr=1763113 |zbl=0984.05044

|volume = 50

|year = 2000

}}.

• {{citation

| last1 = Myrvold | first1 = Wendy | author1-link = Wendy Myrvold

| last2 = Woodcock | first2 = Jennifer

| issue = 1

| journal = Electronic Journal of Combinatorics

| pages = P1.16

| title = A large set of torus obstructions and how they were discovered

| volume = 25

| year = 2018| doi = 10.37236/3797 | doi-access = free

}}

• {{citation

| last1 = Neufeld | first1 = Eugene

| last2 = Myrvold | first2 = Wendy | author2-link = Wendy Myrvold

| chapter = Practical toroidality testing

| pages = 574–580 |isbn=978-0-89871-390-9

| title = Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

| chapter-url = https://dl.acm.org/doi/10.5555/314161.314392

| year = 1997}}.

• {{citation

| last1 = Orbanić | first1 = Alen

| last2 = Pisanski | first2 = Tomaž | author2-link = Tomaž Pisanski

| last3 = Randić | first3 = Milan | author3-link = Milan Randić

| last4 = Servatius | first4 = Brigitte | author4-link = Brigitte Servatius

| issue = 1

| journal = Math. Commun.

| pages = 91–103 |citeseerx=10.1.1.361.2772 |url=http://users.wpi.edu/~bservat/blanusa08.pdf

| title = Blanuša double

| volume = 9

| year = 2004}}.

Category:Graph families

Category:Topological graph theory