Structure derived from halfedges

The halfedge description $M=(E,s,\rho)$ of an oriented surface contains all the information. It is nevertheless convenient to introduce some more derived stucture. For an edge $e\in E$ we define

$\textrm{left}(e)=$ the face (cycle of $s$) containing $e$

$\textrm{right}(e)=$ the face (cycle of $s$) containing $\rho(e)$

$\textrm{start}(e)=$ the vertex (cycle of $s\circ\rho$) containing $e$

$\textrm{end}(e)=$ the vertex (cycle of $s\circ\rho$) containing $\rho(e)$

$\textrm{unorient}(e)=$ the unoriented edge (cycle of $\rho$) containing $e$.

Denote by $F$ the set of all faces of $M$, by $V$ the set of all vertices and by $\tilde{E}$ the set of all unoriented edges.

If we look at the quintuple $(E,V,\rho,\textrm{start},\textrm{end})$ we see finite sets $E,V$, an involution $\rho: E \rightarrow E$ without fixed points and two maps $\textrm{start},\textrm{end}: E \rightarrow V$ such that

$\textrm{start} \circ \rho = \textrm{end}$

This is a one of the possible descriptions of a general finite graph. This graph is called the 1-skeleton or edge-graph of $M$. In a computer graphics context one might also call it the wireframe of $M$.

The two most simple discrete surfaces

We claim that any pair of permutations $s,\rho$ of a finite set $E$ (with $\rho$ involutive and without fixpoints) defines a unique cell decomposition of some compact surface without boundary. No further conditions are needed. To illustrate this, we look at the simplest possible cases where $E=\{e,\tilde{e}\}$ has only two elements. Then necessarily $\rho(e) = \tilde{e}$ and $\rho(\tilde{e})=e$. For $s$ we have two possibilities:

1) $s=id_E$. Then we have two faces, the first one $\varphi$ being bounded by the single edge $e$, the second one $\tilde{\varphi}$ bounded by $\tilde{e}$. We have $s\circ \rho = \rho$ and therefore only one vertex $v$. This is a cell-decomposition of the sphere as shown in the picture below.

2) $s=\rho$. Then we have only one face bounded by the the edge $e$ followed by the edge $\tilde{e}$. We have $s\circ \rho = id_E$ and therefore two vertices $v$ (with a single outgoing edge $e$) and $\tilde{v}$ (with a single outgoing edge $\tilde{e}$). This is also a cell-decomposition of the sphere.

Halfedge description of oriented surfaces

Imagine a cell decomposition $M$ of an oriented compact surface without boundary. Denote by $E$ the set of all oriented edges of $M$. Then for each $e \in E$ there is a unique face $\varphi$ on the left of $e$. Denote by $s(e)$ the oriented edge following $e$ in the cycle of oriented edges in the boundary of $\varphi$. Then

$s: E \rightarrow E$

is a bijective map (a permutation of the elements of $E$). Denote by

$\rho: E \rightarrow E$

the map that assigns to $e$ the same edge with the opposite orientation. Then $\rho$ has no fixed points and satisfies

$\rho^2 = \textrm{id}_E$.

We claim that the whole cell-decomposition can be uniquely recontructed from the permution $s$ and the involution $\rho$ without fixed points: The set of faces $F$ can be recovered from $s,\rho$ as the set of cycles of $s$. A cycle of $s$ is a subset $\varphi \subset E$ which is invariant under $s$ (meaning $s(\varphi)  = \varphi$) that cannot be decomposed in any way into smaller invariant subsets. Similarly, the outgoing oriented edges from a vertex $v$ are cycles of the permutation

$s\circ \rho : E \rightarrow E$.

Finally, unoriented edges $\epsilon$ are represented as cycles of $\rho$.