<p>A <em>combinatorial embedding</em> or <em>signed rotation system</em> is a combinatorial representation of a cellular embedding of a graph on some surface.  An <em>embedding</em> is a drawing of the graph such that no two edges cross; an embedding is <em>cellular</em> if every face is a disk.</p>

<p>Consider an undirected graph $G=(V,E)$.  It is helpful to regard each edge in $E$ as a pair of directed edges, or <em>darts</em>.  Each dart goes from one vertex, called its <em>tail</em>, to another vertex, called its <em>head</em>.  The <em>reversal</em> of a dart is obtained by swapping its head and its tail.  Let $\vec{E}$ denote the set of all darts.</p>

<p>A signed rotation system consists of two functions:</p>

<ul>
<li><p>A successor permutation $\textit{succ} \colon \vec{E} \to \vec{E}$.  Specifically, $\textit{succ}(\vec{e})$ is the next incoming dart after $\vec{e}$ in "clockwise" order around $\textit{head}(\vec{e})$.  Thus, the cycles of $\textit{succ}$ correspond precisely to the vertices of $G$.</p></li>
<li><p>A sign function $\textit{sign}\colon E \to \{-1, +1\}$, which indicates for each edge whether the "clockwise" orders at the endpoints of that edge are consistent ($+1$) or inconsistent ($-1$). </p></li>
</ul>

<p>This representation is not unique.  For example, reversing the cyclic order of incoming darts at any vertex $v$ and changing the signs of all edges incident to $v$ leaves the embedding intact.</p>

<p>The theorem you are asking about is the following:</p>

<blockquote>
  <p><em>Any cellular embedding of any graph $G$ can be encoded by a signed rotation system, such that for some spanning tree $T$, every edge in $T$ is positive.</em></p>
</blockquote>

<p>In fact, one can prove a stronger statement:</p>

<blockquote>
  <p><em>For <strong>any</strong> spanning tree $T$ of any graph $G$, any cellular embedding of $G$ can be encoded by a signed rotation system, such that every edge in $T$ is positive.</em></p>
</blockquote>

<p>If the underlying surface is orientable, we can choose a global "clockwise" orientation, which means any embedding onto that surface has a representation where <em>all</em> edges in $G$ are positive.</p>

<p>On the other hand, if the underlying surface is non-orientable, some edges <em>must</em> be negative.  Any one-sided cycle must include an odd number of negative edges (and therefore at least one negative edge), because moving once around a one-sided cycle reverses your local orientation.  That's what "one-sided" <em>means</em>.  Still, it is possible to ensure that every edge in your favorite spanning tree is positive.</p>

<p>The proof is straightforward induction over the tree $T$.</p>

CC BY-SA 3.0
2013-05-24T16:05:47.317Z
following statement : all cycles are two-sided => underlying surface of the embedding is orientable , proof : transform pi to pi` with lambda(T) = 1 on some some tree (all tree edges are 1) , some non tree edges lies in a cycle which uses even -1 edges (cause every cycle is two-sided) hence lambda(G) = 1 now look at the polygon representation of S, every edge appears twice once foward and once backward and hence every curve is twosided in S. is this correct ?
dominik85
CC BY-SA 3.0
2013-05-26T00:35:40.870Z
I prefer the proof "by definition of orientable".  You can also simplify your proof by considering only fundamental cycles.  Make every edge in the psanning tree positive.  Every fundamental cycle has exactly one non-tree edge, which must be positive because the cycle is two-sided.  On the other hand, every non-tree edge lies in a fundamental cycle.  So all edges are positive.  So the surface has a consistent global orientation.
Jeffε
CC BY-SA 3.0
2013-05-23T21:18:31.890Z
2013-05-23T21:18:31.890Z
Jeffε
<p>I have a problem with the following statement :</p>

<p>Every combinatorial embedding is equivalent to one with $\lambda(T) = 1$ on a spanning tree of G</p>

<p>What does this mean ? </p>

<p>OK in a spanning tree there isn't a cycle, so the signature of every edge is equal to $1$ but what is the sense of this statement? </p>

CC BY-SA 3.0
2013-05-23T16:35:54.463Z
Could you provide slightly more context?
András Salamon
<graph-theory><co.combinatorics><topological-graph-theory>
combinatorical embedding
dominik85
# combinatorical embedding

(Asked by: username_0 on 2013-05-23)

I have a problem with the following statement :

Every combinatorial embedding is equivalent to one with $\lambda(T) = 1$ on a spanning tree of G

What does this mean ?

OK in a spanning tree there isn't a cycle, so the signature of every edge is equal to $1$ but what is the sense of this statement?

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

> **Comments:**
> **username_1**: Could you provide slightly more context?  

---

## 1 answers

### Answer by username_2 on 2013-05-23. Score: 5

A *combinatorial embedding* or *signed rotation system* is a combinatorial representation of a cellular embedding of a graph on some surface. An *embedding* is a drawing of the graph such that no two edges cross; an embedding is *cellular* if every face is a disk.

Consider an undirected graph $G=(V,E)$. It is helpful to regard each edge in $E$ as a pair of directed edges, or *darts*. Each dart goes from one vertex, called its *tail*, to another vertex, called its *head*. The *reversal* of a dart is obtained by swapping its head and its tail. Let $\vec{E}$ denote the set of all darts.

A signed rotation system consists of two functions:

* A successor permutation $\textit{succ} \colon \vec{E} \to \vec{E}$. Specifically, $\textit{succ}(\vec{e})$ is the next incoming dart after $\vec{e}$ in "clockwise" order around $\textit{head}(\vec{e})$. Thus, the cycles of $\textit{succ}$ correspond precisely to the vertices of $G$.
* A sign function $\textit{sign}\colon E \to \{-1, +1\}$, which indicates for each edge whether the "clockwise" orders at the endpoints of that edge are consistent ($+1$) or inconsistent ($-1$).

This representation is not unique. For example, reversing the cyclic order of incoming darts at any vertex $v$ and changing the signs of all edges incident to $v$ leaves the embedding intact.

The theorem you are asking about is the following:

> *Any cellular embedding of any graph $G$ can be encoded by a signed rotation system, such that for some spanning tree $T$, every edge in $T$ is positive.*

In fact, one can prove a stronger statement:

> *For **any** spanning tree $T$ of any graph $G$, any cellular embedding of $G$ can be encoded by a signed rotation system, such that every edge in $T$ is positive.*

If the underlying surface is orientable, we can choose a global "clockwise" orientation, which means any embedding onto that surface has a representation where *all* edges in $G$ are positive.

On the other hand, if the underlying surface is non-orientable, some edges *must* be negative. Any one-sided cycle must include an odd number of negative edges (and therefore at least one negative edge), because moving once around a one-sided cycle reverses your local orientation. That's what "one-sided" *means*. Still, it is possible to ensure that every edge in your favorite spanning tree is positive.

The proof is straightforward induction over the tree $T$.

> **Comments:**
> **username_0**: following statement : all cycles are two-sided => underlying surface of the embedding is orientable , proof : transform pi to pi` with lambda(T) = 1 on some some tree (all tree edges are 1) , some non tree edges lies in a cycle which uses even -1 edges (cause every cycle is two-sided) hence lambda(G) = 1 now look at the polygon representation of S, every edge appears twice once foward and once backward and hence every curve is twosided in S. is this correct ?  
> **username_2**: I prefer the proof "by definition of orientable".  You can also simplify your proof by considering only fundamental cycles.  Make every edge in the psanning tree positive.  Every fundamental cycle has exactly one non-tree edge, which must be positive because the cycle is two-sided.  On the other hand, every non-tree edge lies in a fundamental cycle.  So all edges are positive.  So the surface has a consistent global orientation.  

---

