In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

field of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

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

that can be embedded on a

torus In geometry, a torus (: tori or toruses) is a surface of revolution generated by revolving a circle in three-dimensional space one full revolution about an axis that is coplanarity, coplanar with the circle. The main types of toruses inclu ...

. 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 In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

is also a toroidal graph. A toroidal graph that cannot be embedded in a plane is said to have

genus Genus (; : genera ) is a taxonomic rank above species and below family (taxonomy), family as used in the biological classification of extant taxon, living and fossil organisms as well as Virus classification#ICTV classification, viruses. In bino ...

1. The

Heawood graph In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood. Combinatorial properties The graph is cubic, and all cycles in the graph have six or more edges. ...

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

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

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

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, for example, has crossing number 4 and is toroidal.

Properties

Any toroidal graph has

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

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 graph, simple, planar graph can be Graph drawing, drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as ...

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

. 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 graph, planar embedding of a Graph (discrete mathematics), graph to embeddings in a ''book'', a collection of half-planes all having the same Line (geometry), line as their boundary ...

s with at most 7 pages.

Obstructions

By the

Robertson–Seymour theorem In graph theory, the Robertson–Seymour theorem (also called the graph minors 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 ...

, 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, 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 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 (discrete mathematics), graph that encodes the abstract structure of a group (mathematics), group. Its definition is sug ...

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

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