Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is a follow-up and an improvement (I hope), to Is the dual graph simple?

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with $n\geq 0$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every edge the corresponding faces have in common in the original graph.

Let $G$ be cellularly embedded in some surface of genus $n$ and let $G'$ be the dual of this embedding.

What conditions on the embedding of $G$ (necessary and/or sufficient) ensure that $G'$ is a simple graph (at most one edge between two vertices and no loops)?

share|improve this question

2 Answers 2

A loop in the dual graph means that there is an edge in the original graph that has the same face on both sides. This means that this edge is a bridge (i.e. if that edge is removed, the graph is no longer connected). Also, every bridge gives rise to a loop in the dual graph.

A double edge in the dual graph means that there are two faces that share two edges in the original graph. This means that the original graph will no longer be connected if you remove the two edges.

So, a good sufficient condition for a simple dual graph is 3-connectedness (which incidentally also makes the embedding on the sphere unique up to continuous deformations).

share|improve this answer
    
I can see how these statements are true in the sphere. How can I be sure that they stay true in the sphere with $n$ handles? –  becko Jun 10 '12 at 0:44
    
Ok, sorry, I just didn't see that. I will think about it later. –  Phira Jun 10 '12 at 0:45
    
It's ok. It was helpful anyway. –  becko Jun 10 '12 at 0:49
    
I now see it. Both statements are definetely not true for the torus. Thanks anyway. –  becko Jun 10 '12 at 0:51
    
+1 I think this answer is helpful. In a torus, the removal of an edge that has the same face on both sides does not alter the connectivity, but it gives a new graph that can be drawn in the sphere, i.e., the edge removal lowers the genus by 1. And the removal of two edges shared by the same two faces does the same. This is assuming, of course, that the original graph has genus 1. –  becko Jun 10 '12 at 2:58

Say the embedding of $G$ is of genus $n>0$. Then:

  1. $e'\in E(G')$ is a loop if and only if deleting the dual edge $e\in E(G)$ from the embedding of $G$ gives an embedding of genus $n-1$.
  2. $e'$ and $f'$ have the same endpoints (i.e., they are multiedges) if and only if deleting the dual edges $e$ and $f$ from the embedding of $G$ gives an embedding of genus $n-1$.

These statements follow from Euler's formula $\chi=V-E+F=2-2n$. In case (1.) above, deleting $e$ lowers $E$ by one and adds one to $F$. In case (2.), deleting $e$ and $f$ lowers $E$ by two and leaves $F$ unchanged. In both cases $\chi$ is increased in two, which means that $n$ is lowered by one.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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