Rotation system

Rotation systems are a discrete way to encode orientable maps. They can be extended to encode non-orientable maps as well.

Idea[edit | edit source]

Maps are a way of embedding a graph with particular properties. The same map can be embedded multiple ways on multiple surfaces. Rotation systems specify how each vertex looks locally, by specifying an order for the edges. If we say that two edges are next to each other in the embedding we know they both belong to a common face. Furthermore we know that faces are made by either always making only left turns or only right turns, so if we specify the order of edges around a vertex (e.g. clockwise) then we can make the faces by always following the leftmost turn.

Rotation systems can allow us a simple way to create purely combinatorial representations for maps. This can be useful for computer search and processing, or for concise visual communication.

Definition[edit | edit source]

The rotation system for a tetrahedron with the face permutation added for demonstration. The edge permutation, $ψ$ , is indicated with blue single-tipped arrows; the vertex permutation, $φ$ , is indicated with red double-tipped arrows and the face permutation, $\psi \circ \varphi$ , is indicated with green single-barbed arrows.

A rotation system is a triple $(X,\psi ,\phi )$ such that:^[1]

$X$ is a set. Elements of $x$ are called darts.
$ψ$ is a permutation on $X$ such that $\psi (\psi (x))=x$ for every dart $x$ and $ψ$ has no fixed points.
$φ$ is a permutation on $X$ .

From here we can define vertices, edges and faces:

A vertex is an orbit of a dart under $φ$ . That is for some dart $x$ it is the set of all darts such that $y=\psi ^{n}(x)$ for some integer $n$ .
An edge is an orbit of a dart under $ψ$ . Since $ψ$ is an involution each edge has two darts: $x$ and $\psi (x)$ .
A face is the orbit of a dart under $\psi \circ \varphi$ . The number of darts in the orbit correspond to the number of edges / vertices incident on the face.

Two elements are incident on another if their intersection is non-empty.

Isomorphism[edit | edit source]

We say that two rotation systems $(X,\psi ,\varphi )$ and $(X',\psi ',\varphi ')$ are isomorphic if there exists a bijection $f:X\leftrightarrow X'$ such that:^[2]

$f\circ \psi =\psi '\circ f$
$f\circ \varphi =\varphi '\circ f$

Extension to non-orientable maps[edit | edit source]

The rotation system of a hemicube. It is identical to the rotation system of the tetrahedron but with all of its edges barred.

Since rotation systems can only express orientable maps it is desirable to extend this encoding to represent non-orientable maps as well. To do this we allow rotation systems to have some edges which reverse orientation. Edges that reverse orientation are called barred edges^[2] and can be indicated in diagrams by drawing a bar through the edge.^[2] Intuitively when determining the faces of a map crossing barred edges causes the direction of the $φ$ permutation to reverse replacing it with $\varphi ^{-1}$ .

Conceretely this can be defined as follows. Consider a rotation system $(X,\psi :X\leftrightarrow X,\varphi :X\rightarrow X)$ and a function $\iota :X\rightarrow \{1,-1\}$ where $\iota (x)$ is -1 when $x$ is on a barred edge and 1 otherwise. We require that $\iota (\psi (x))=\iota (x)$ , that is that $ι$ is consistent for both darts incident on an edge. From here we define two additional functions: