Dual graph
In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual of G, then G is a dual of H (if G is connected). The same notion of duality may also be used for more general embeddings of graphs on manifolds.
Contents |
[edit] Properties
- The dual of a planar graph is a planar multigraph - multiple edges.[1]
- If G is a connected graph and if G′ is a dual of G then G is a dual of G′.
- Dual graphs are not unique, in the sense that the same graph can have non-isomorphic dual graphs because the dual graph depends on a particular plane embedding. In the picture, red graphs are not isomorphic because the upper one has a vertex with degree 6 (the outer region).
Because of the dualism, any result involving counting regions and vertices can be dualized by exchanging them.
[edit] Algebraic dual
Let G be a connected graph. An algebraic dual of G is a graph G★ so that G and G★ have the same set of edges, any cycle of G is a cut of G★, and any cut of G is a cycle of G★. Every planar graph has an algebraic dual which is in general not unique (any dual defined by a plane embedding will do). The converse is actually true, as settled by Whitney:[2]
- A connected graph G is planar if and only if it has an algebraic dual.
The same fact can be expressed in the theory of matroids: if M is the graphic matroid of a graph G, then the dual matroid of M is a graphic matroid if and only if G is planar. If G is planar, the dual matroid is the graphic matroid of the dual graph of G.
[edit] Weak dual
The weak dual of an embedded planar graph is the subgraph of the dual graph whose vertices correspond to the bounded faces of the primal graph. A planar graph is outerplanar if and only if its weak dual is a forest, and a planar graph is a Halin graph if and only if its weak dual is biconnected and outerplanar. For any embedded planar graph G, let G+ be the multigraph formed by adding a single new vertex v in the unbounded face of G, and connecting v to each vertex of the outer face (multiple times, if a vertex appears multiple times on the boundary of the outer face); then, G is the weak dual of the planar dual of G+.[3][4]
[edit] Notes
- ^ Here we consider that graphs may have loops and multiple edges to avoid uncommon considerations
- ^ Whitney, Hassler (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society 34: 339–362.
- ^ Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society 38: 215–219, MR0389672.
- ^ Sysło, Maciej M.; Proskurowski, Andrzej (1983), "On Halin graphs", Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, 1018, Springer-Verlag, pp. 248–256, doi:10.1007/BFb0071635.
[edit] External links
- Weisstein, Eric W., "Dual graph" from MathWorld.
- Weisstein, Eric W., "Self-dual graph" from MathWorld.
