4
$\begingroup$

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)?

2 Answers 2

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

  • 0
    I think this generalizes to any genus. Thus if for a graph of genus $n$ there is an embedding in which an edge has the same face on both side, then the removal of that edge from the graph gives a graph of genus $n-1$. Similarly, if for a graph of genus $n$ there is an embedding in which two edges are shared by the same two faces, then the removal of those two edges gives a graph of genus $n-1$. I'm not strong in topological graph theory, though, so I don't know how to prove this (hence I am not sure it's true)2012-06-10
0

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.