Rotationsordninger

Rotationsordninger, in the context of graph theory, are a way to describe how the edges around each vertex of a graph are arranged in a cyclic order. Formally, a rotationsordning assigns to every vertex a cyclic permutation of the incident edges. This local data, when combined with the incidence structure of the graph, determines a cellular embedding of the graph into a surface.

From a rotationsordning, one can derive a global embedding by tracing faces: start on an edge, move to the adjacent vertex, and at that vertex follow the next edge in the prescribed cyclic order. Repeating this process partitions the edges into closed walks that bound the faces of the embedded graph. The resulting embedding may be on an orientable surface (such as a sphere or torus) or on a non‑orientable surface, depending on the global orientation implied by the rotation data.

Genus and faces: Using Euler’s formula, V − E + F = 2 − 2g for orientable embeddings (where g is the genus), or V − E + F = 2 − k for non‑orientable embeddings (where k is the non‑orientable genus). Thus, a rotationsordning not only encodes a topological embedding but also allows computation of the surface’s genus if the embedding is known.

Applications and relation to planarity: Rotationsordninger are central in topological graph theory, enabling the description and enumeration of graph embeddings on surfaces, map drawing, and genus calculations. A graph is planar if there exists a rotationsordning yielding an embedding on the sphere (genus 0). They also underpin algorithms for recognizing embeddings and for constructing drawings with prescribed topological properties.