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$:


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.


1 Answer 1

  • 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$.
  • $\begingroup$ 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? $\endgroup$
    – a06e
    Jun 29, 2012 at 2:03
  • $\begingroup$ 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$. $\endgroup$
    – Arnaud
    Jun 29, 2012 at 2:55
  • $\begingroup$ Let me give it some more thought. $\endgroup$
    – a06e
    Jun 29, 2012 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.