Given a graph $G$, a rotation system for $G$ is composed of two elements:$\pi = \{\pi_v: v\in V(G)\}$, where $\pi_v$ is a cyclic permutation of the edges incident on $v$. Thus if $e$ is an edge incident on $v$, $\pi_v(e)$ is another edge incident on $v$, and we say that $\pi_v(e)$ comes after $e$ at $v$.$\lambda:E(G)\rightarrow \{-1,1\}$ is a function that assigns to each edge a sign $\pm 1$.Given a rotation system for a graph $G$, we define a face-walk as a walk in $G$:$$v_0e_1v_1e_2v_2...e_nv_0$$such that:$e_{i+1}=\pi_{v_i}^{r_i}(e_i)$ for $1\leq i<n$;$e_1=\pi_{v_0}(e_n)$;$\lambda(e_1)\lambda(e_2)...\lambda(e_n)=1$.Here, $r_i=\lambda(e_1)\lambda(e_2)...\lambda(e_i)$ and $\pi_v^{-1}$ denotes the inverse cyclic permutation to $\pi_v$ (that is, $\pi_v^{-1}(e)$ gives the edge that comes before $e$ at $v$).According to Theorem 3.2.2 in Topological Graph Theory by Gross and Tucker:Every rotation system on a graph $G$ defines (up to equivalence of imbeddings) a unique locally oriented graph imbedding $G\rightarrow S$. Conversely, every locally oriented graph imbedding $G\rightarrow S$ defines a rotation system for $G$.In the same book, an algorithm is given to trace the faces of the embedding. One starts with any vertex $v_0$ and any edge $e_1$ incident on $v_0$ and proceeds to complete a face-walk. They claim that this will give a face boundary of the embedding. To understand this, I need to see a proof for the following two statements:Given any vertex $v_0$ and any edge $e_1$ incident on $v_0$, one can complete a face-walk starting at $v_0e_1$. Clearly a sequence $v_0e_1v_1e_2v_2...$ can be extended indefinetely. The question is whether this sequence will be periodic.Each edge either belongs to exactly two distinct face-walks (and appears once in each), or it appears exactly twice in one face-walk.Neither of these claims is proved in the book.
Face-walks in rotation systems for graphs
graph theory;co.combinatorics;topological graph theory
If the sequence $v_0e_1v_1...$ is extended indefinetely without going back to $v_0e_1$, then since the graph is finite, some couple vertex-edge is repeated and hence it is periodic (since the facewalk always continues the same way after meeting this couple vertex-edge), so it looks like $v_0e_1v_1e_2.. v_{i-1}e_{i}v_ie_{i+1}...v_{i+j}e_{i+j+1}v_ie_{i+1}...v_i...v_i$ and so on indefinitely. We can assume that $e_i\neq e_{i+j+1}$ otherwise the loop never starts. But then we have $e_{i+1}=\pi_{v_i}(e_i)$ and $e_{i+1}=\pi_{v_i}(e_{i+j+1})$, so $e_i=e_{i+j+1}$, yielding a contradiction. (I intentionnaly left out the $\lambda$ for the sake of clarity, but it works the same for non-pure rotation systems by replacing couple (vertex-edge) by triple (vertex-edge-value of $r_i$ when arriving at the vertex)).For an edge $e$ attached to vertices $v_1$ and $v_2$, $e$ appears in the facewalks starting by $v_1 e$ and $v_2 e$ (possibly the same facewalk !). Moreover, it only appears in facewalks including $v_1 e$ and $v_2 e$ (where would it come from otherwise ?), so that makes exactly two facewalks (or twice the same). Edit : To be more precise, a facewalk is uniquely defined by a triple (vertex-edge-value of $r_i$ when arriving at that edge). But arriving at $v_1 e$ with orientation (value of $r_i$) -1 yields the same facewalk (up to reversing it) as arriving at $v_2 e$ with orientation +1, so there really are only two different facewalks passing through $e$.