Toroidal graph

From Wikipedia, the free encyclopedia

In mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. Usually, it is assumed that G is also non-planar.

Contents 1 Examples 2 Properties 3 See also 4 References

[edit] Examples

The Heawood graph, the complete bipartite graph, and all Möbius ladders are toroidal. More generally, any graph with crossing number 1 is toroidal.

[edit] Properties

Any toroidal graph has chromatic number at most 7 (Heawood 1890) and any triangle-free toroidal graph has chromatic number at most 4 (Kronk and 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 (Kocay et al 2001). Furthermore, the analogue of Tutte's spring theorem applies in this case (Gortler et al. 2006). Toroidal graphs also have book embeddings with at most 7 pages (Endo 1997).

[edit] See also

• planar graph
• topological graph theory

[edit] References

• 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. MR1475841.

• 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. MR2189438.

• Heawood, P. J. (1890). "Map colouring theorems". Quarterly J. Math. Oxford Ser. 24: 322–339.

• Kocay, W.; Neilson, D.; Szypowski, R. (2001). "Drawing graphs on the torus". Ars Combinatoria 59: 259–277. MR1832459.

• Kronk, Hudson V.; White, Arthur T. (1972). "A 4-color theorem for toroidal graphs". Proceedings of the American Mathematical Society 34 (1): 83–86. DOI:10.2307/2037902. MR0291019.

• Neufeld, Eugene; Myrvold, Wendy (1997). "Practical toroidality testing". Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 574–580.