2
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Could you provide slightly more context? $\endgroup$ May 23, 2013 at 16:35

1 Answer 1

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$
    – dominik85
    May 24, 2013 at 16:05
  • $\begingroup$ 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. $\endgroup$
    – Jeffε
    May 26, 2013 at 0:35

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.