1
$\begingroup$

How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?

In the post linked above, the user "plop" gives a great response where they claim, in particular, that a plane graph $G$ has a well-defined geometric dual. Paraphrasing, for any two drawings $G^*_1$ and $G^*_2$ obtained in the following way, there exists a unique planar graph $Y$, up to isomorphism, such that the plane graphs $G_1^*$ and $G_2^*$ are planar embeddings of $Y$. Consequently, we may write $G^*$ for either $G_1^*$ or $G_2^*$, and call it the geometric dual of $G$.

To obtain such a plane graph $G^*$ from $G$, draw a point in$^\dagger$ each face of $G$, and for each arc $e$ of $G$, draw a new arc passing once through $e$ connecting the points in the two faces $f_1$ and $f_2$ incident with $e$. Do this such that no two of these new arcs intersect.$^{\dagger\dagger}$ This new set of points together with this new set of arcs describes the plane graph $G^*$.

$^\dagger$To make complete sense of this construction, one needs at least the Jordan Curve Theorem, and according to "plop" also needs the Jordan-Shoenflies Theorem. $^{\dagger\dagger}$By the way, shouldn't this also require us to use the fact that a topological subspace of $\mathbb R^2$ (or of $S^2$) is connected if and only if it is path-connected? (Otherwise I could imagine two curves technically not intersecting but with something pathological happening where the curves get arbitrarily close to each other and end up "crossing" while still being curves in the sense that they are topological embeddings of $[0,1]$. This is a little beside the point.)

I am ok with the above claim. My question is:

Does there exist a planar graph $X$ with two planar embeddings $G_1$ and $G_2$ such that $G_1^*$ and $G_2^*$ are the planar embeddings of nonisomorphic graphs $Y_1$ and $Y_2$? If so, what's an example construction. If not, why not?

Note: Wikipedia claims seems to claim that the answer is "yes", but doesn't provide an example. I put a [citation needed] tag, so maybe once this is resolved, we can link it back to here.

The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

https://en.wikipedia.org/wiki/Dual_graph

$\endgroup$

1 Answer 1

2
$\begingroup$

There is an answer in Graph Theory by Bondy and Murty:

enter image description here

It is clear that both graphs are isomorphic. Their respective duals are not, because each face of the first dual has degree 3 (except the unbounded one, of degree 5), and there are two faces of degree 4 in the second dual.

$\endgroup$
1
  • $\begingroup$ This is exactly what I was looking for! Thanks! $\endgroup$ Commented May 14, 2021 at 3:09

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.