Toroidal graph

In the

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,^[1] 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.^[2]

Properties

Any toroidal graph has

Any triangle-free toroidal graph has chromatic number at most 4.^[5]

By a result analogous to

Toroidal graphs also have book embeddings with at most 7 pages.^[8]

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

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

Notes

References

• 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,
  MR 1475841
  .
• Gortler, Steven J.; Gotsman, Craig; Thurston, Dylan (2006), "Discrete one-forms on meshes and applications to 3D mesh parameterization" (PDF), Computer Aided Geometric Design, 23 (2): 83–112,
  S2CID 135438
  .
• Heawood, P. J. (1890), "Map colouring theorems", Quarterly Journal of Mathematics, First Series, 24: 322–339.
• Kocay, W.; Neilson, D.; Szypowski, R. (2001), "Drawing graphs on the torus" (PDF), Ars Combinatoria, 59: 259–277,
  MR 1832459, archived from the original
  (PDF) on 2004-12-24, retrieved 2018-09-06.
• Kronk, Hudson V.; White, Arthur T. (1972), "A 4-color theorem for toroidal graphs",
  MR 0291019
  .
• Zbl 0984.05044
  .
• doi:10.37236/3797
• Neufeld, Eugene;
  ISBN 978-0-89871-390-9
  .
• Orbanić, Alen;
  CiteSeerX 10.1.1.361.2772
  .