Dual graph

Historically, the first form of graph duality to be recognized was the association of the Platonic solids into pairs of dual polyhedra.

The dual of a simple graph need not be simple: it may have self-loops (an edge with both endpoints at the same vertex) or multiple edges connecting the same two vertices, as was already evident in the example of dipole multigraphs being dual to cycle graphs.

Removing the edges of a cutset necessarily splits the graph into at least two connected components.

[16] In a connected planar graph G, every simple cycle of G corresponds to a minimal cutset in the dual of G, and vice versa.

[19] This duality extends from individual cutsets and cycles to vector spaces defined from them.

[22] A spanning tree may be defined as a set of edges that, together with all of the vertices of the graph, forms a connected and acyclic subgraph.

Symmetrically, if S is connected, then the edges dual to the complement of S form an acyclic subgraph.

Therefore, when S has both properties – it is connected and acyclic – the same is true for the complementary set in the dual graph.

Any spanning tree and its complementary dual spanning tree partition the edges into two subsets of V − 1 and F − 1 edges respectively, and adding the sizes of the two subsets gives the equation which may be rearranged to form Euler's formula.

According to Duncan Sommerville, this proof of Euler's formula is due to K. G. C. Von Staudt’s Geometrie der Lage (Nürnberg, 1847).

The extra edges, in combination with paths in the spanning trees, can be used to generate the fundamental group of the surface.

Another given by Harary involves the handshaking lemma, according to which the sum of the degrees of the vertices of any graph equals twice the number of edges.

For any plane graph G, let G+ be the plane multigraph formed by adding a single new vertex v in the unbounded face of G, and connecting v to each vertex of the outer face (multiple times, if a vertex appears multiple times on the boundary of the outer face); then, G is the weak dual of the (plane) dual of G+.

When all faces are bounded regions surrounded by a cycle of the graph, an infinite planar graph embedding can also be viewed as a tessellation of the plane, a covering of the plane by closed disks (the tiles of the tessellation) whose interiors (the faces of the embedding) are disjoint open disks.

[38] The concept of a dual tessellation can also be applied to partitions of the plane into finitely many regions.

The sites on the convex hull of the input give rise to unbounded Voronoi polygons, two of whose sides are infinite rays rather than finite line segments.

Each vertex of the Delaunay triangle is positioned within its corresponding face of the Voronoi diagram.

The concept of duality can be extended to graph embeddings on two-dimensional manifolds other than the plane.

This duality can be explained by modeling the flow network as a spanning tree on a grid graph of an appropriate scale, and modeling the drainage divide as the complementary spanning tree of ridgelines on the dual grid graph.

[47] In computer vision, digital images are partitioned into small square pixels, each of which has its own color.

[48] In computational geometry, the duality between Voronoi diagrams and Delaunay triangulations implies that any algorithm for constructing a Voronoi diagram can be immediately converted into an algorithm for the Delaunay triangulation, and vice versa.

Lloyd's algorithm, a method based on Voronoi diagrams for moving a set of points on a surface to more evenly spaced positions, is commonly used as a way to smooth a finite element mesh described by the dual Delaunay triangulation.

This method improves the mesh by making its triangles more uniformly sized and shaped.

[50] In the synthesis of CMOS circuits, the function to be synthesized is represented as a formula in Boolean algebra.

One of the two circuits is derived by converting the conjunctions and disjunctions of the formula into series and parallel compositions of graphs, respectively.

The other circuit reverses this construction, converting the conjunctions and disjunctions of the formula into parallel and series compositions of graphs.

[52] The duality of convex polyhedra was recognized by Johannes Kepler in his 1619 book Harmonices Mundi.

[53] Recognizable planar dual graphs, outside the context of polyhedra, appeared as early as 1725, in Pierre Varignon's posthumously published work, Nouvelle Méchanique ou Statique.

[54] In connection with the four color theorem, the dual graphs of maps (subdivisions of the plane into regions) were mentioned by Alfred Kempe in 1879, and extended to maps on non-planar surfaces by Lothar Heffter [de] in 1891.

[55] Duality as an operation on abstract planar graphs was introduced by Hassler Whitney in 1931.