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 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.
Properties
Any toroidal graph has
chromatic number at most 7. The
complete graph K7 provides an example of a toroidal graph with chromatic number 7.
[4]
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
See also
Notes
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 ,
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",
Proceedings of the American Mathematical Society , 34 (1), American Mathematical Society: 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,
CiteSeerX
10.1.1.28.7183 ,
hdl :
10338.dmlcz/133137 ,
MR
1763113 ,
Zbl
0984.05044 .
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,
ISBN
978-0-89871-390-9 .
Orbanić, Alen;
Pisanski, Tomaž ;
Randić, Milan ;
Servatius, Brigitte (2004),
"Blanuša double" (PDF) ,
Math. Commun. , 9 (1): 91–103,
CiteSeerX
10.1.1.361.2772 .