<ul>
<li>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)).</li>
<li>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$.</li>
</ul>

CC BY-SA 3.0
2012-06-29T02:03:48.637Z
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?
a06e
CC BY-SA 3.0
2012-06-29T02:55:07.860Z
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
CC BY-SA 3.0
2012-06-29T21:25:15.050Z
Let me give it some more thought.
a06e
CC BY-SA 3.0
2012-06-27T01:11:45.743Z
2012-06-27T01:35:06.150Z
2012-06-27T01:35:06.150Z
Arnaud
<p>Given a graph $G$, a rotation system for $G$ is composed of two elements:</p>

<ul>
<li>$\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$.</li>
<li>$\lambda:E(G)\rightarrow \{-1,1\}$ is a function that assigns to each edge a sign $\pm 1$.</li>
</ul>

<p>Given a rotation system for a graph $G$, we define a <strong>face-walk</strong> as a walk in $G$:</p>

<p>$$v_0e_1v_1e_2v_2...e_nv_0$$</p>

<p>such that:</p>

<ul>
<li>$e_{i+1}=\pi_{v_i}^{r_i}(e_i)$ for $1\leq i&lt;n$;</li>
<li>$e_1=\pi_{v_0}(e_n)$;</li>
<li>$\lambda(e_1)\lambda(e_2)...\lambda(e_n)=1$.</li>
</ul>

<p>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$).</p>

<p>According to Theorem 3.2.2 in Topological Graph Theory by Gross and Tucker:</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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, <strong>I need to see a proof for the following two statements</strong>:</p>

<ul>
<li>Given any vertex $v_0$ and any edge $e_1$ incident on $v_0$, one <strong>can</strong> 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.</li>
<li>Each edge either belongs to exactly two distinct face-walks (and appears once in each), or it appears exactly twice in one face-walk.</li>
</ul>

<p>Neither of these claims is proved in the book.</p>

<graph-theory><co.combinatorics><topological-graph-theory>
Face-walks in rotation systems for graphs
a06e
# Face-walks in rotation systems for graphs

(Asked by: username_0 on 2012-06-26)

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* $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.

**Tags:** graph-theory, co.combinatorics, topological-graph-theory


---

## 1 answers

### Answer by username_1 on 2012-06-27. Score: 4 | Accepted answer

* 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$.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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$.  
> **username_0**: Let me give it some more thought.  

---

