.
Dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex corresponding to each face of G, and an edge joining two neighboring faces for each edge in 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 in manifolds.
The notion described in this page is different from the edge-to-vertex dual (Line graph) of a graph and should not be confused with it.
The red graph is the dual graph of the blue graph.
Properties
Two red graphs are duals for the blue one, but they are not isomorphic.
The dual of a plane graph is a plane multigraph - multiple edges.[1]
If G is a connected plane graph and if G′ is the dual of G then G is isomorphic to the dual of G′.
Since the dual graph depends on a particular embedding, the dual graph of a planar graph is not unique in the sense that the same planar graph can have non-isomorphic dual graphs. In the picture, the red graphs are not isomorphic because the upper one has a vertex with degree 6 (the outer face). However, if the graph is 3-connected, then Whitney showed that the embedding, and thus the dual graph, is unique.[2]
Because of the duality, any result involving counting faces and vertices can be dualized by exchanging them.
Algebraic dual
Let G be a connected graph. An algebraic dual of G is a graph G★ such 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 Hassler Whitney in the Whitney's planarity criterion:[3]
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.
Weak dual
The weak dual of a plane graph is the subgraph of the dual graph whose vertices correspond to the bounded faces of the primal graph. A plane graph is outerplanar if and only if its weak dual is a forest, and a plane graph is a Halin graph if and only if its weak dual is biconnected and outerplanar. For any plane graph G, let G+ be the plane 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 (plane) dual of G+.[4][5]
Notes
Here we consider that graphs may have loops and multiple edges to avoid uncommon considerations.
Bondy, Adrian; Murty, U.S.R. (2008), "Planar Graphs", Graph Theory, Graduate Texts in Mathematics 244, Springer, p. 267, doi:10.1007/978-1-84628-970-5, ISBN 9781846289699, LCCN 2007923502, "Theorem 10.28"
Whitney, Hassler (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society 34 (2): 339–362, doi:10.1090/S0002-9947-1932-1501641-2.
Fleischner, Herbert J.; Geller, D. P.; Harary, Frank (1974), "Outerplanar graphs and weak duals", Journal of the Indian Mathematical Society 38: 215–219, MR 0389672.
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.
External links
Weisstein, Eric W., "Dual graph", MathWorld.
Weisstein, Eric W., "Self-dual graph", MathWorld.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
