Dual graph

In the mathematical discipline of graph theory, the dual graph of a plane graph G is a graph that has a vertex for each face of G. The dual graph has an edge whenever two faces of G 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 e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs (graphs that are already embedded in the plane) rather than planar graphs (graphs that may be embedded but for which the embedding is not yet known). 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 algebraically 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.However, 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 H is a dual of a connected graph G, then G is a dual of H. When discussing the dual of a graph G, the graph G 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 (without parallel edges or self-loops) 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. 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 n-cycle, these two regions are separated from each other by n different edges. Therefore, the dual graph of the n-cycle is a multigraph with two vertices (dual to the regions), connected to each other by n dual edges. Such a graph is called a dipole graph. Conversely, the dual to an n-edge dipole graph is an n-cycle. According to Steinitz's theorem, every polyhedral graph (the graph formed by the vertices and edges of a three-dimensional convex polyhedron) 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. 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 (the pyramids). However, there also exist self-dual graphs that are not polyhedral, such as the one shown. Servatius & Christopher (1992) 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 n vertices has exactly 2n − 2 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.