In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a toroidal graph is a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

that can be embedded on a

torus In geometry, a torus (plural tori, colloquially donut or doughnut) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis that is coplanar with the circle. If the axis of revolution does not tou ...

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

Examples

Any graph that can be embedded in a plane can also be embedded in a torus. A toroidal graph of

genus Genus ( plural genera ) is a taxonomic rank used in the biological classification of living and fossil organisms as well as viruses. In the hierarchy of biological classification, genus comes above species and below family. In binomial nom ...

1 can be embedded in a torus but not in a plane. The

Heawood graph Heawood is a surname. Notable people with the surname include: * Jonathan Heawood, British journalist *Percy John Heawood (1861–1955), British mathematician **Heawood conjecture ** Heawood graph **Heawood number In mathematics, the Heawood numbe ...

, the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

K₇ (and hence K₅ and K₆), the

Petersen graph In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is n ...

(and hence the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...

K_3,3, since the Petersen graph contains a subdivision of it), one of the Blanuša snarks, and all

Möbius ladder In graph theory, the Möbius ladder , for even numbers , is formed from an by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of (the utili ...

s 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 In the mathematical field of graph theory, the Möbius–Kantor graph is a symmetric bipartite cubic graph with 16 vertices and 24 edges named after August Ferdinand Möbius and Seligmann Kantor. It can be defined as the generalized Petersen gra ...

, for example, has crossing number 4 and is toroidal.

Properties

Any toroidal graph has

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices ...

at most 7. The

K₇ provides an example of a toroidal graph with chromatic number 7. Any triangle-free toroidal graph has chromatic number at most 4. By a result analogous to

Fáry's theorem In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straigh ...

, any toroidal graph may be drawn with straight edges in a rectangle with periodic boundary conditions. Furthermore, the analogue of

Tutte's spring theorem In graph drawing and geometric graph theory, a Tutte embedding or barycentric embedding of a simple, 3-vertex-connected, planar graph is a crossing-free straight-line embedding with the properties that the outer face is a convex polygon and that ...

applies in this case. Toroidal graphs also have

book embedding In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie ...

s with at most 7 pages.

Obstructions

By the

Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering. Equivalently, every family of graphs that is c ...

, 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 graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

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 In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...

ordering. A graph is toroidal if and only if it has none of these graphs as a topological minor.

Gallery

File:Cayley graphs of the quaternion group.png, Two isomorphic

Cayley graph In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...

s of the

quaternion group In group theory, the quaternion group Q8 (sometimes just denoted by Q) is a non-abelian group of order eight, isomorphic to the eight-element subset \ of the quaternions under multiplication. It is given by the group presentation :\mathrm_8 ...

. File:Cayley graph of quaternion group on torus.png,

of the

embedded in the torus. File:Quaternion group.webm, Video of

of the

embedded in the torus. File:Heawood graph and map on torus.png, The

and associated map embedded in the torus. File:Pappus-graph-on-torus.png, The

Pappus graph In the mathematical field of graph theory, the Pappus graph is a bipartite 3- regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek ...

and associated map embedded in the torus.

Notes

References

*. *. *. *. *. *. *. * *. *{{citation , last1 = Orbanić , first1 = Alen , last2 = Pisanski , first2 = Tomaž , author2-link = Tomaž Pisanski , last3 = Randić , first3 = Milan , author3-link = Milan Randić , last4 = Servatius , first4 = Brigitte , author4-link = Brigitte Servatius , issue = 1 , journal = Math. Commun. , pages = 91–103 , citeseerx=10.1.1.361.2772 , url=http://users.wpi.edu/~bservat/blanusa08.pdf , title = Blanuša double , volume = 9 , year = 2004. Graph families Topological graph theory

Examples

Properties

Obstructions

Gallery

See also

Notes

References