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
$\begingroup$
$\endgroup$
5
-
$\begingroup$ "the dual graph of a planar graph is planar" hence the answer is yes $\endgroup$– emonHRDec 31, 2019 at 17:13
-
$\begingroup$ Dual graph includes the outer region of the original graph as a vertice $\endgroup$– אמנון ברטורDec 31, 2019 at 17:13
-
$\begingroup$ What is the proof of that? $\endgroup$– אמנון ברטורJan 1, 2020 at 13:37
-
$\begingroup$ here is one @אמנון ברטור $\endgroup$– emonHRJan 1, 2020 at 13:43
-
$\begingroup$ Hi אמנון ברטור, did you see that your question has been answered? Please mark it "accepted" if it solves your problem. $\endgroup$– JamesJan 9 at 6:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The short answer is "yes": a graph is planar if and only if its dual is also planar.
The proof outline is as follows:
- 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.
- 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.
