Toroidal graph

In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

 G is toroidal if it can be embedded

Embedding

In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....

 on the torus

Torus

In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...

. 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

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 complete graph

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

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

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 named for Julius Petersen, who in 1898 constructed it...

 (and hence the complete bipartite graph

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

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

Blanuša snarks

In the mathematical field of graph theory, the Blanuša snarks are two 3-regular graphs with 18 vertices and 27 edges. They were discovered by Croatian mathematician Danilo Blanuša in 1946 and are named after him. When discovered, only one snark was known—the Petersen graph.As snarks, the Blanuša...

, and all Möbius ladder

Möbius ladder

In graph theory, the Möbius ladder Mn is a cubic circulant graph with an even number n of vertices, formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle...

s are toroidal. More generally, any graph with crossing number

Crossing number (graph theory)

In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...

 1 is toroidal. Some graphs with greater crossing numbers are also toroidal: the Möbius–Kantor graph

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

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

Properties

Any toroidal graph has chromatic number at most 7. The complete graph

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

 K₇ provides an example of toroidal graph with chromatic number 7.

Any triangle-free

Triangle-free graph

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...

 toroidal graph has chromatic number at most 4.

By a result analogous to Fáry's theorem

Fáry's theorem

In mathematics, 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 straight line segments does not allow a larger class of graphs to be drawn...

, any toroidal graph may be drawn

Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...

 with straight edges in a rectangle with periodic boundary conditions. Furthermore, the analogue of Tutte's spring theorem

Fáry's theorem

In mathematics, 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 straight line segments does not allow a larger class of graphs to be drawn...

 applies in this case.
Toroidal graphs also have book embedding

Book embedding

In graph theory, book embedding is a generalization of planar embedding to nonplanar surfaces in the form of a book, a collection of pages joined together at the spine of the book . The vertices of the graph are embedded on the spine, and each edge must lie in one of the pages...

s with at most 7 pages.