rotationsschema

Rotationsschema, or rotation scheme, is a combinatorial description used in graph theory and topological graph theory to specify how a graph can be drawn on a surface without edge crossings. It encodes the cyclic order of the edges (or half-edges) incident to each vertex, and, together with a pairing of opposite ends of each edge, determines an embedding of the graph into a surface. This approach allows one to reason about embeddings abstractly, without reference to a specific geometric drawing.

Formally, let G = (V, E) be a graph. For every edge e = {u, v} there are two darts (half-edges), one at each endpoint. A rotation at a vertex v is a cyclic ordering of the darts incident to v. The collection of such cyclic orders for all vertices constitutes the rotation system. Along with a pairing that matches the two darts of each edge, the rotation system defines a cellular embedding of G into a surface. The faces of the embedding correspond to orbits of the permutation obtained by composing the vertex rotations with the edge-pairing.

Rotationsschema are central to the study of map theory and embeddings, providing a compact way to compute the genus of the surface via Euler’s formula, and to classify embeddings up to isomorphism. Variants include rotation schemes that incorporate a signature to handle non-orientable surfaces. They also underpin algorithms for testing planarity, enumerating embeddings, and computing automorphisms of embedded graphs. In practice, rotation schemes offer a rigorous framework for translating between combinatorial data and topological realizations of graphs.