Dual geometric graph of a planar graph

115 Views Asked by At

Does the dual geometric graph of a planar graph have a planar embedding? Aplanar graph is a graph that can be embedded in the plane such that any edges can cross each other at their end points only Dual graph is generated from a planar graph by representing each face as a vertic And connecting two vertices by an edge if there is a boundery edge between the faces represented by the vertices

1

There are 1 best solutions below

0
On

The short answer is "yes": a graph is planar if and only if its dual is also planar.

The proof outline is as follows:

  1. A graph can be drawn without crossing edges on the plane (i.e., is planar) if and only if it can be drawn without crossing edges on the sphere.
  2. Given a spherical embedding of a planar graph without crossings, you can trivially construct a spherical embedding of its dual without crossings by connecting the centres of adjacent faces with straight lines. That gives you a non-crossing spherical embedding of the dual, proving that the dual is planar.

If you also want a proof-sketch for (1), let me know. The construction is similarly easy.