TOPICS
Search

Dual Graph


DualGraphDualGraphExample

Given a planar graph G, a geometric dual graph and combinatorial dual graph can be defined. Whitney showed that these are equivalent (Harary 1994), so that one may speak of "the" dual graph G^*. The illustration above shows the process of constructing a geometric dual graph.

Polyhedral graphs have unique dual graphs. While some nonpolyhedral planar graphs also 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 consequently a unique dual, iff it is a subdivision of a polyhedral graph. The complete bipartite graph K_(2,4) is an example of a planar nonpolyhedral graph that is not 3-vertex-connected but whose embeddings are all isomorphic, meaning its dual graphs are also isomorphic.

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, "DualGraphName"].

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

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.

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