[[File:Toroidal graph sample.gif|thumb|

A cubic graph with 14 vertices embedded on a torus]]

thumb|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 K<sub>7</sub> (and hence K<sub>5</sub> and K<sub>6</sub>), the Petersen graph (and hence the complete bipartite graph K<sub>3,3</sub>, since the Petersen graph contains a subdivision of it), one of the Blanuša snarks, 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 K<sub>7</sub> 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. 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>

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

File:Cayley graph of quaternion group on torus.png|Cayley graph of the quaternion group embedded in the torus.

File:Quaternion group.webm|Video of Cayley graph of the quaternion group embedded in the torus.

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

</gallery>

See also

  • Grünbaum–Nash-Williams conjecture, on Hamiltonian cycles in 4-vertex-connected toroidal graphs
  • Topological graph theory
  • Toroidal polyhedron

Notes

References

  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .
  • .