Toroidal graph

Short description: Graph able to be embedded on a torus

A cubic graph with 14 vertices embedded on a torus

The Heawood graph and associated map embedded in the torus.

In the mathematical field of graph theory, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices and edges 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 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, 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.

Properties

Any toroidal graph has chromatic number at most 7. The complete graph K₇ provides an example of a toroidal graph with chromatic number 7.

Any triangle-free toroidal graph has chromatic number at most 4.

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. Furthermore, the analogue of Tutte's spring theorem applies in this case. Toroidal graphs also have book embeddings with at most 7 pages.

Obstructions

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.

Gallery

• 

  Two isomorphic Cayley graphs of the quaternion group.

• 

  Cayley graph of the quaternion group embedded in the torus.

• 

  Video of Cayley graph of the quaternion group embedded in the torus.

• 

  The Pappus graph and associated map embedded in the torus.

See also

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

References

• Chromatic graph theory, CRC Press, 2008, ISBN 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:10.1016/S0012-365X(96)00144-6 .
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), "Discrete one-forms on meshes and applications to 3D mesh parameterization", Computer Aided Geometric Design 23 (2): 83–112, doi:10.1016/j.cagd.2005.05.002, http://www.cs.jhu.edu/~misha/Fall09/Gortler05.pdf .
• "Map colouring theorems", Quarterly Journal of Mathematics, First Series 24: 322–339, 1890 .
• Kocay, W.; Neilson, D.; Szypowski, R. (2001), "Drawing graphs on the torus", Ars Combinatoria 59: 259–277, http://bkocay.cs.umanitoba.ca/g&g/articles/Torus.pdf, retrieved 2018-09-06 .
• Kronk, Hudson V.; White, Arthur T. (1972), "A 4-color theorem for toroidal graphs", Proceedings of the American Mathematical Society (American Mathematical Society) 34 (1): 83–86, doi:10.2307/2037902 .
• Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Math. Slovaca 50: 117–121 .
• "A large set of torus obstructions and how they were discovered", Electronic Journal of Combinatorics 25 (1): P1.16, 2018, doi:10.37236/3797 
• Neufeld, Eugene (1997), "Practical toroidality testing", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 574–580, ISBN 978-0-89871-390-9, https://dl.acm.org/doi/10.5555/314161.314392 .
• Orbanić, Alen (2004), "Blanuša double", Math. Commun. 9 (1): 91–103, http://users.wpi.edu/~bservat/blanusa08.pdf .