Dual graph
In the mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex for each face of. The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge of has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of . The definition of the dual depends on the choice of embedding of the graph, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.
Historically, the first form of graph duality to be recognized was the association of the Platonic solids into pairs of dual polyhedra. Graph duality is a topological generalization of the geometric concepts of dual polyhedra and dual tessellations, and is in turn generalized combinatorially by the concept of a dual matroid. Variations of planar graph duality include a version of duality for directed graphs, and duality for graphs embedded onto non-planar two-dimensional surfaces.
These notions of dual graphs should not be confused with a different notion, the edge-to-vertex dual or line graph of a graph.
The term dual is used because the property of being a dual graph is symmetric, meaning that if is a dual of a connected graph, then is a dual of. When discussing the dual of a graph, the graph itself may be referred to as the "primal graph". Many other graph properties and structures may be translated into other natural properties and structures of the dual. For instance, cycles are dual to cuts, spanning trees are dual to the complements of spanning trees, and simple graphs are dual to 3-edge-connected graphs.
Graph duality can help explain the structure of mazes and of drainage basins. Dual graphs have also been applied in computer vision, computational geometry, mesh generation, and the design of integrated circuits.
Examples
Cycles and dipoles
The unique planar embedding of a cycle graph divides the plane into only two regions, the inside and outside of the cycle, by the Jordan curve theorem. However, in an -cycle, these two regions are separated from each other by different edges. Therefore, the dual graph of the -cycle is a multigraph with two vertices, connected to each other by dual edges. Such a graph is called a multiple edge, linkage, or sometimes a dipole graph. Conversely, the dual to an -edge dipole graph is an -cycle.Dual polyhedra
According to Steinitz's theorem, every polyhedral graph must be planar and 3-vertex-connected, and every 3-vertex-connected planar graph comes from a convex polyhedron in this way. Every three-dimensional convex polyhedron has a dual polyhedron; the dual polyhedron has a vertex for every face of the original polyhedron, with two dual vertices adjacent whenever the corresponding two faces share an edge. Whenever two polyhedra are dual, their graphs are also dual. For instance the Platonic solids come in dual pairs, with the octahedron dual to the cube, the dodecahedron dual to the icosahedron, and the tetrahedron dual to itself. Polyhedron duality can also be extended to duality of higher dimensional polytopes, but this extension of geometric duality does not have clear connections to graph-theoretic duality.Self-dual graphs
A plane graph is said to be self-dual if it is isomorphic to its dual graph. The wheel graphs provide an infinite family of self-dual graphs coming from self-dual polyhedra. However, there also exist self-dual graphs that are not polyhedral, such as the one shown. describe two operations, adhesion and explosion, that can be used to construct a self-dual graph containing a given planar graph; for instance, the self-dual graph shown can be constructed as the adhesion of a tetrahedron with its dual.It follows from Euler's formula that every self-dual graph with vertices has exactly edges. Every simple self-dual planar graph contains at least four vertices of degree three, and every self-dual embedding has at least four triangular faces.
Properties
Many natural and important concepts in graph theory correspond to other equally natural but different concepts in the dual graph. Because the dual of the dual of a connected plane graph is isomorphic to the primal graph, each of these pairings is bidirectional: if concept in a planar graph corresponds to concept in the dual graph, then concept in a planar graph corresponds to concept in the dual.Simple graphs versus multigraphs
The dual of a simple graph need not be simple: it may have self-loops or multiple edges connecting the same two vertices, as was already evident in the example of dipole multigraphs being dual to cycle graphs. As a special case of the cut-cycle duality discussed below,the bridges of a planar graph are in one-to-one correspondence with the self-loops of the dual graph. For the same reason, a pair of parallel edges in a dual multigraph corresponds to a 2-edge cutset in the primal graph. Therefore, a planar graph is simple if and only if its dual has no 1- or 2-edge cutsets; that is, if it is 3-edge-connected. The simple planar graphs whose duals are simple are exactly the 3-edge-connected simple planar graphs. This class of graphs includes, but is not the same as, the class of 3-vertex-connected simple planar graphs. For instance, the figure showing a self-dual graph is 3-edge-connected but is not 3-vertex-connected.
Uniqueness
Because 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 blue graphs are isomorphic but their dual red graphs are not. The upper red dual has a vertex with degree 6 while in the lower red graph all degrees are less than 6.Hassler Whitney showed that if the graph is 3-connected then the embedding, and thus the dual graph, is unique. By Steinitz's theorem, these graphs are exactly the polyhedral graphs, the graphs of convex polyhedra. A planar graph is 3-vertex-connected if and only if its dual graph is 3-vertex-connected. Moreover, a planar biconnected graph has a unique embedding, and therefore also a unique dual, if and only if it is a subdivision of a 3-vertex-connected planar graph.
For some planar graphs that are not 3-vertex-connected, such as the complete bipartite graph, the embedding is not unique, but all embeddings are isomorphic. When this happens, correspondingly, all dual graphs are isomorphic.
Because different embeddings may lead to different dual graphs, testing whether one graph is a dual of another is a nontrivial algorithmic problem. For biconnected graphs, it can be solved in polynomial time by using the SPQR trees of the graphs to construct a canonical form for the equivalence relation of having a shared mutual dual. For instance, the two red graphs in the illustration are equivalent according to this relation. However, for planar graphs that are not biconnected, this relation is not an equivalence relation and the problem of testing mutual duality is NP-complete.
Cuts and cycles
A cutset in an arbitrary connected graph is a subset of edges defined from a partition of the vertices into two subsets, by including an edge in the subset when it has one endpoint on each side of the partition. Removing the edges of a cutset necessarily splits the graph into at least two connected components. A minimal cutset is a cutset with the property that every proper subset of the cutset is not itself a cut. A minimal cutset of a connected graph necessarily separates its graph into exactly two components, and consists of the set of edges that have one endpoint in each component. A simple cycle is a connected subgraph in which each vertex of the cycle is incident to exactly two edges of the cycle.In a connected planar graph, every simple cycle of corresponds to a minimal cutset in the dual of, and vice versa. This can be seen as a form of the Jordan curve theorem: each simple cycle separates the faces of into the faces in the interior of the cycle and the faces of the exterior of the cycle, and the duals of the cycle edges are exactly the edges that cross from the interior to the exterior. The girth of any planar graph equals the edge connectivity of its dual graph.
This duality extends from individual cutsets and cycles to vector spaces defined from them. The cycle space of a graph is defined as the family of all subgraphs that have even degree at each vertex; it can be viewed as a vector space over the two-element finite field, with the symmetric difference of two sets of edges acting as the vector addition operation in the vector space. Similarly, the cut space of a graph is defined as the family of all cutsets, with vector addition defined in the same way. Then the cycle space of any planar graph and the cut space of its dual graph are isomorphic as vector spaces. Thus, the rank of a planar graph equals the cyclotomic number of its dual and vice versa. A cycle basis of a graph is a set of simple cycles that form a basis of the cycle space. For edge-weighted planar graphs the minimum-weight cycle basis of the graph is dual to the Gomory–Hu tree of the dual graph, a collection of nested cuts that together include a minimum cut separating each pair of vertices in the graph. Each cycle in the minimum weight cycle basis has a set of edges that are dual to the edges of one of the cuts in the Gomory–Hu tree. When cycle weights may be tied, the minimum-weight cycle basis may not be unique, but in this case it is still true that the Gomory–Hu tree of the dual graph corresponds to one of the minimum weight cycle bases of the graph.
In directed planar graphs, simple directed cycles are dual to directed cuts. Strongly oriented planar graphs are dual to directed acyclic graphs in which no edge belongs to a cycle. To put this another way, the strong orientations of a connected planar graph are dual to acyclic orientations. In the same way, dijoins are dual to feedback arc sets.