- Toroidal graph
[
A graph (similar to theHeawood graph ) embedded on thetorus such that no edges cross. ]In
mathematics , a graph "G" is toroidal if it can be embedded on thetorus . 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.Examples
The
Heawood graph , thecomplete bipartite graph K3,3, and allMöbius ladder s are toroidal. More generally, any graph with crossing number 1 is toroidal.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 havebook embedding s with at most 7 pages (Endo 1997).See also
*
planar graph
*topological graph theory References
* | doi = 10.1016/S0012-365X(96)00144-6
* | doi = 10.1016/j.cagd.2005.05.002
*
*
*
*
Wikimedia Foundation. 2010.
