Toroidal graph

From Wikipedia, the free encyclopedia
A cubic graph with 14 vertices embedded on a torus
The Heawood graph and associated map embedded in the torus.

In mathematics, a toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross.

Examples[]

Any graph which can be embedded in a plane can also be embedded in a torus. A toroidal graph of genus 1 can be embedded in a torus but not in a plane. The Heawood graph, the complete graph K7 (and hence K5 and K6), the Petersen graph (and hence the complete bipartite graph K3,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 chromatic number at most 7.[3] The complete graph K7 provides an example of toroidal graph with chromatic number 7.[4]

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

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.[6] Furthermore, the analogue of Tutte's spring theorem applies in this case.[7] 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 topological minor ordering. A graph is toroidal if and only if it has none of these graphs as a topological minor.[9]

Gallery[]

See also[]

Notes[]

  1. ^ Orbanić et al. (2004).
  2. ^ Marušič & Pisanski (2000).
  3. ^ Heawood (1890).
  4. ^ Chartrand & Zhang (2008).
  5. ^ Kronk & White (1972).
  6. ^ Kocay, Neilson & Szypowski (2001).
  7. ^ Gortler, Gotsman & Thurston (2006).
  8. ^ Endo (1997).
  9. ^ Myrvold & Woodcock (2018).

References[]

  • Chartrand, Gary; Zhang, Ping (2008), Chromatic graph theory, CRC Press, 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, 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, doi:10.1016/j.cagd.2005.05.002, MR 2189438.
  • 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", Proceedings of the American Mathematical Society, American Mathematical Society, 34 (1): 83–86, doi:10.2307/2037902, JSTOR 2037902, MR 0291019.
  • Marušič, Dragan; Pisanski, Tomaž (2000), "The remarkable generalized Petersen graph G(8,3)", Math. Slovaca, 50: 117–121[permanent dead link].
  • Myrvold, Wendy; Woodcock, Jennifer (2018), "A large set of torus obstructions and how they were discovered", Electronic Journal of Combinatorics, 25 (1): P1.16, doi:10.37236/3797
  • Neufeld, Eugene; Myrvold, Wendy (1997), "Practical toroidality testing", Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 574–580.
  • Orbanić, Alen; Pisanski, Tomaž; Randić, Milan; Servatius, Brigitte (2004), "Blanuša double", , 9 (1): 91–103.
Retrieved from ""