close
Image TOPICS
Image
Search

Rotation System


A rotation system is a combinatorial way to encode a graph embedding on a surface. Instead of drawing an explicit embedding of a graph, the cyclic order of the graph edges around each graph vertex is instead recorded. The collection of these cyclic orders for all vertices (i.e., "rotations" at each vertex) then gives a rotation system. This cyclic order determines how edges are arranged locally and therefore determines the embedding up to homeomorphism.

A rotation system allows the graph faces of an embedding to be computed without any explicit drawing. However, rotation systems are not unique; different cyclic orders can produce different embeddings of the same graph.

To construct a rotation system, replace each edge by two oppositely directed darts and at each vertex specify a list of darts based on which dart comes next when turning around the vertex in a counterclockwise direction.

A rotation system completely determines the vertices, edges, and faces of a cellular embedding, and therefore also determines the genus of the surface using the Euler characteristic. For a connected graph with v vertices, e edges, and f faces in an orientable cellular embedding, the genus is

 g=1-1/2(v-e+f).

This makes rotation systems useful for counting planar embeddings, which are precisely the rotation systems of graph genus 0, up to the chosen equivalence of embeddings. Similarly, the graph genus of a graph can be found by minimizing the genus over all rotation systems of the graph. This combinatorial viewpoint is often known as the Heffter-Edmonds-Ringel rotation principle (Gross and Tucker 1987, Mohar and Thomassen 2001).

Covering embeddings can also be described compactly using voltage graphs.


See also

Cellular Embedding, Graph Embedding, Graph Genus, Planar Embedding, Planar Graph, Voltage Graph

Explore with Wolfram|Alpha

References

Gross, J. L. and Tucker, T. W. Topological Graph Theory. New York: Wiley, 1987.Lando, S. K. and Zvonkin, A. K. Graphs on Surfaces and Their Applications. Berlin, Germany: Springer-Verlag, 2004.Mohar, B. and Thomassen, C. Graphs on Surfaces. Baltimore, MD: Johns Hopkins University Press, 2001.Stahl, S. "The Embedding of a Graph--A Survey." J. Graph Th. 2, 275-298, 1978.

Cite this as:

Weisstein, Eric W. "Rotation System." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RotationSystem.html

Subject classifications