# Face-walks in rotation systems for graphs

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.

• 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$.
• I completely understand the first point, but I no longer think the second point is alright. You say: "But arriving at $v_1e$ with orientation -1 yields the same facewalk (up to reversing it) as arriving at $v_2e$ with orientation +1". I don't think this is right. It depends on the orientation of the edge before $e$. I haven't figured it out yet. Maybe I am missing something. Can you be more explicit with the second point? – becko Jun 29 '12 at 2:03
• What I call orientation is the value of $r_i$ before $e$. Let's see what happens if $\lambda(e)=1$. If I arrive at $v_1$ from an edge $e_0$ with orientation +1, I turn according to $\pi_{v_1}$ and continue with the edge $e$. Since $\lambda(e)=1$, I arrive at $v_2$ and turn according to $\pi_{v_2}$, which gives an edge $e_2$. Conversely, if I arrive at $v_2$ from edge $e_2$ with orientation $-1$, I turn according to $\pi_{v_2}^{-1}$ and get the edge $e$, then to $v_1$ where I turn according to $\pi_{v_1}^{-1}$ which gives $e_0$. So both are the same walks. The same works for $\lambda(e)=-1$. – Arnaud Jun 29 '12 at 2:55
• Let me give it some more thought. – becko Jun 29 '12 at 21:25