TOPICS
Search

Dual Graph


DualGraph

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 unqiuely 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.

DualGraphExample

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

E^*=E
(1)
F^*=V
(2)
V^*=F
(3)

between dual and primal edge, face, and vertex counts. They also of course satisfy the polyhedral formula

V+F-E=2
(4)
V^*+F^*-E^*=2.
(5)

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 Graph

Explore with Wolfram|Alpha

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 Graph

Cite this as:

Weisstein, Eric W. "Dual Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DualGraph.html

Subject classifications