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 Embedded or embedding (alternatively imbedded or imbedding) may refer to: Science * Embedding, in mathematics, one instance of some mathematical object contained within another instance ** Graph embedding * Embedded generation, a distributed ge ...

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

. 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 n ...

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 See also *Heywood (surname) He ...

, 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 ...

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

Petersen graph In the mathematics, mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertex (graph theory), vertices and 15 edge (graph theory), edges. It is a small graph that serves as a useful example and counterexample for ...

(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 ...

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 utilit ...

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 grap ...

, 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 o ...

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, any toroidal graph may be drawn with straight edges in a rectangle with

periodic boundary conditions Periodic boundary conditions (PBCs) are a set of boundary conditions which are often chosen for approximating a large (infinite) system by using a small part called a ''unit cell''. PBCs are often used in computer simulations and mathematical mode ...

. Furthermore, the analogue of Tutte's spring theorem 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 o ...

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 i ...

, 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 i ...

in ''H''. That is, ''H'' forms the set of

forbidden minors In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden ...

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

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 Ca ...

s of the

quaternion group In group theory, the quaternion group Q8 (sometimes just denoted by Q) is a nonabelian group, non-abelian group (mathematics), group of Group order, order eight, isomorphic to the eight-element subset \ of the quaternions under multiplication. ...

. 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 m ...

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