Dual Graph
Given a planar graph G with a particular planar embedding, a geometric dual graph and combinatorial dual graph can be defined. Whitney (1932) showed that these are equivalent for planar graphs (Fleischner 1973, Harary 1994. p. 115) so that one may speak of "the" dual graph G^*. The illustration above shows the process of constructing a geometric dual graph from a planar nonpolyhedral graph, leading to a multigraph.
While some nonpolyhedral planar graphs have a unique dual, a general planar graph has multiple dual graphs depending on the choice of planar embedding. A planar graph has a unique embedding (and hence is said to be uniquely embeddable), and consequently a unique dual, iff it is a graph subdivision of a polyhedral graph. The complete bipartite graph K_(2,4) is an example of a planar nonpolyhedral graph whose embeddings are all isomorphic, meaning its dual graphs are also isomorphic and it is uniquely embeddable.
On the other hand, polyhedral graphs have unique dual graphs. The dual graph G^* of a polyhedral graph G has graph vertices each of which corresponds to a face of G and each of whose faces corresponds to a graph vertex of G. Two nodes in G^* are connected by an graph edge if the corresponding faces in G have a boundary graph edge in common. As a result, each edge of a graph G has a corresponding dual edge e^* in G^* corresponding to the edge that connects the two faces on either side of e, meaning the edge counts are the same. Combined with the switching of the roles of faces and vertices, this gives the relations
between dual and primal edge, face, and vertex counts. They also of course satisfy the polyhedral formula
The dual graph of a wheel graph is itself a wheel (Skiena 1990, p. 147). In general, a graph that is dual to itself is called a self-dual graph.
The notation of duality can be generalized to embeddings other than those in the plane and hence to nonplanar graphs. This is closely related to the concept of double covers.
Graph duals of named graphs are implemented in the Wolfram Language as GraphData [graph, "DualGraph"].
The Tutte polynomial of the dual graph G^* of a graph G is given by
| T_(G^*)(x,y)=T_G(y,x), |
(6)
|
i.e., by swapping the variables of the Tutte polynomial of the original graph.
See also
Combinatorial Dual Graph, Geometric Dual Graph, Planar Graph, Self-Dual GraphExplore with Wolfram|Alpha
More things to try:
References
Fleischner, H. "The Uniquely Embeddable Planar Graphs." Disc. Math. 4, 347-358, 1973.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 113-114, 1994.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Wagon, S. "An April Fool's Hoax." Mathematica in Educ. Res. 7, 46-52, 1998.Wagon, S. Mathematica in Action, 2nd ed. New York: Springer-Verlag, pp. 536-537, 1999.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.Referenced on Wolfram|Alpha
Dual GraphCite this as:
Weisstein, Eric W. "Dual Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DualGraph.html