![Duals graphs](https://upload.wikimedia.org/wikipedia/commons/b/ba/Duals_graphs.svg)
In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
discipline of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the dual graph of a
plane graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cros ...
is a graph that has a
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
* Vertex (computer graphics), a data structure that describes the positio ...
for each
face
The face is the front of an animal's head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may aff ...
of . The dual graph has an
edge
Edge or EDGE may refer to:
Technology Computing
* Edge computing, a network load-balancing system
* Edge device, an entry point to a computer network
* Adobe Edge, a graphical development application
* Microsoft Edge, a web browser developed by ...
for each pair of faces in that are separated from each other by an edge, and a
self-loop
In graph theory, a loop (also called a self-loop or a ''buckle'') is an edge that connects a vertex to itself. A simple graph contains no loops.
Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow ...
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 (graphs that are already embedded in the plane) rather than
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
s (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 solid
In geometry, a Platonic solid is a convex, regular polyhedron in three-dimensional Euclidean space. Being a regular polyhedron means that the faces are congruent (identical in shape and size) regular polygons (all angles congruent and all edges c ...
s into pairs of
dual polyhedra
In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. ...
. Graph duality is a
topological
In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
generalization of the geometric concepts of dual polyhedra and
dual tessellation
In geometry, every polyhedron is associated with a second dual structure, where the Vertex (geometry), vertices of one correspond to the Face (geometry), faces of the other, and the edges between pairs of vertices of one correspond to the edges b ...
s, and is in turn generalized combinatorially by the concept of a
dual matroid
In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it...
Matroid duals go back to the original paper by Hassler ...
. Variations of planar graph duality include a version of duality for
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
s, 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
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edges of . is constructed in the following way: for each edge in , make a vertex in ; for every ...
of a graph.
The term ''
dual'' is used because the property of being a dual graph is
symmetric
Symmetry (from grc, συμμετρία "agreement in dimensions, due proportion, arrangement") in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definiti ...
, meaning that if is a dual of a
connected graph
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
, 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 tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s 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
maze
A maze is a path or collection of paths, typically from an entrance to a goal. The word is used to refer both to branching tour puzzles through which the solver must find a route, and to simpler non-branching ("unicursal") patterns that lea ...
s and of
drainage basin
A drainage basin is an area of land where all flowing surface water converges to a single point, such as a river mouth, or flows into another body of water, such as a lake or ocean. A basin is separated from adjacent basins by a perimeter, t ...
s. Dual graphs have also been applied in
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
,
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
,
mesh generation
Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells.
Often these cells form a simplicial complex.
Usually the cells partition the geometric input domain. ...
, and the design of
integrated circuit
An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...
s.
Examples
Cycles and dipoles
The unique planar embedding of a
cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
divides the plane into only two regions, the inside and outside of the cycle, by the
Jordan curve theorem
In topology, the Jordan curve theorem asserts that every '' Jordan curve'' (a plane simple closed curve) divides the plane into an " interior" region bounded by the curve and an " exterior" region containing all of the nearby and far away exteri ...
. 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
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...
with two vertices (dual to the regions), connected to each other by dual edges. Such a graph is called a multiple edge, linkage, or sometimes a
dipole graph
In graph theory, a dipole graph, dipole, bond graph, or linkage, is a multigraph consisting of two vertices connected with a number of parallel edges. A dipole graph containing edges is called the dipole graph, and is denoted by . The dipol ...
. Conversely, the dual to an -edge dipole graph is an -cycle.
Dual polyhedra
![Dual Cube-Octahedron](https://upload.wikimedia.org/wikipedia/commons/e/e7/Dual_Cube-Octahedron.svg)
According to
Steinitz's theorem, every
polyhedral graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...
(the graph formed by the vertices and edges of a three-dimensional
convex polyhedron
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
) 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
In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. ...
; 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 solid
In geometry, a Platonic solid is a convex, regular polyhedron in three-dimensional Euclidean space. Being a regular polyhedron means that the faces are congruent (identical in shape and size) regular polygons (all angles congruent and all edges c ...
s 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
polytope
In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...
s, but this extension of geometric duality does not have clear connections to graph-theoretic duality.
Self-dual graphs
![Self-dual graph](https://upload.wikimedia.org/wikipedia/commons/c/ce/Self-dual_graph.svg)
A plane graph is said to be self-dual if it is
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
to its dual graph. The
wheel graph
A wheel is a circular component that is intended to rotate on an axle bearing. The wheel is one of the key components of the wheel and axle which is one of the six simple machines. Wheels, in conjunction with axles, allow heavy objects to be ...
s provide an infinite family of self-dual graphs coming from
self-dual polyhedra (the
pyramid
A pyramid (from el, πυραμίς ') is a structure whose outer surfaces are triangular and converge to a single step at the top, making the shape roughly a pyramid in the geometric sense. The base of a pyramid can be trilateral, quadrilat ...
s).
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
Euler's formula, named after Leonhard Euler, is a mathematical formula in complex analysis that establishes the fundamental relationship between the trigonometric functions and the complex exponential function. Euler's formula states that for an ...
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
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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 (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. As a special case of the cut-cycle duality discussed below,
the
bridges
A bridge is a structure built to span a physical obstacle (such as a body of water, valley, road, or rail) without blocking the way underneath. It is constructed for the purpose of providing passage over the obstacle, which is usually someth ...
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 (that is, a length-2 cycle) corresponds to a 2-edge
cutset
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connec ...
in the primal graph (a pair of edges whose deletion disconnects the 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 (and therefore its dual is simple) but is not 3-vertex-connected.
Uniqueness
![Noniso dual graphs](https://upload.wikimedia.org/wikipedia/commons/7/7b/Noniso_dual_graphs.svg)
Because the dual graph depends on a particular embedding, the dual graph of a
planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...
is not unique, in the sense that the same planar graph can have non-
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
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 (corresponding to the outer face of the blue graph) while in the lower red graph all degrees are less than 6.
Hassler Whitney
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...
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 graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...
s, the graphs of convex polyhedra. A planar graph is 3-vertex-connected if and only if its dual graph is 3-vertex-connected. More generally, a planar graph has a unique embedding, and therefore also a unique dual, if and only if it is a
subdivision
Subdivision may refer to:
Arts and entertainment
* Subdivision (metre), in music
* ''Subdivision'' (film), 2009
* "Subdivision", an episode of ''Prison Break'' (season 2)
* ''Subdivisions'' (EP), by Sinch, 2005
* "Subdivisions" (song), by Rus ...
of a 3-vertex-connected planar graph (a graph formed from a 3-vertex-connected planar graph by replacing some of its edges by paths). For some planar graphs that are not 3-vertex-connected, such as the
complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17.
Graph theory i ...
, 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 (without already knowing their embeddings) is a nontrivial
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
ic problem. For
biconnected graphs, it can be solved in polynomial time by using the
SPQR tree
In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and ...
s of the graphs to construct a
canonical form
In mathematics and computer science, a canonical, normal, or standard form of a mathematical object is a standard way of presenting that object as a mathematical expression. Often, it is one which provides the simplest representation of an obje ...
for the
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each 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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
.
Cuts and cycles
A
cutset
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connec ...
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 (also called a bond) 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
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.
A graph witho ...
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
In topology, the Jordan curve theorem asserts that every '' Jordan curve'' (a plane simple closed curve) divides the plane into an " interior" region bounded by the curve and an " exterior" region containing all of the nearby and far away exteri ...
: 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 (the size of its smallest cycle) equals the
edge connectivity of its dual graph (the size of its smallest cutset).
This duality extends from individual cutsets and cycles to
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
s defined from them. The
cycle space
In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.
This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dime ...
of a graph is defined as the family of all subgraphs that have even
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
at each vertex; it can be viewed as a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
over the
two-element finite field, with the
symmetric difference
In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \.
Th ...
of two sets of edges acting as the vector addition operation in the vector space. Similarly, the
cut space
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connect ...
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
Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as:
Level or position in a hierarchical organization
* Academic rank
* Diplomatic rank
* Hierarchy
* ...
of a planar graph (the
dimension
In physics and mathematics, the dimension of a Space (mathematics), mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any Point (geometry), point within it. Thus, a Line (geometry), lin ...
of its cut space) equals the
cyclotomic number of its dual (the dimension of its cycle space) and vice versa.
A
cycle basis
In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be exp ...
of a graph is a set of simple cycles that form a
basis
Basis may refer to:
Finance and accounting
* Adjusted basis, the net cost of an asset after adjusting for various tax-related items
*Basis point, 0.01%, often used in the context of interest rates
* Basis trading, a trading strategy consisting ...
of the cycle space (every even-degree subgraph can be formed in exactly one way as a symmetric difference of some of these cycles). For
edge-weighted planar graphs (with sufficiently general weights that no two cycles have the same weight) the minimum-weight cycle basis of the graph is dual to the
Gomory–Hu tree
In combinatorial optimization, the Gomory–Hu tree of an undirected graph with capacities is a weighted tree that represents the minimum ''s''-''t'' cuts for all ''s''-''t'' pairs in the graph. The Gomory–Hu tree can be constructed in maximum ...
of the dual graph, a collection of nested cuts that together include a
minimum cut
In graph theory, a minimum cut or min-cut of a graph is a cut (a partition of the vertices of a graph into two disjoint subsets) that is minimal in some metric.
Variations of the minimum cut problem consider weighted graphs, directed graphs, ter ...
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 (partitions of the vertices into two subsets such that all edges go in one direction, from one subset to the other). Strongly oriented planar graphs (graphs whose underlying undirected graph is connected, and in which every edge belongs to a cycle) are dual to
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
s in which no edge belongs to a cycle. To put this another way, the
strong orientation In graph theory, a strong orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that makes it into a strongly connected graph.
Strong orientations have been applied to the design of one-way road networks. ...
s of a connected planar graph (assignments of directions to the edges of the graph that result in a
strongly connected graph) are dual to
acyclic orientation
In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orie ...
s (assignments of directions that produce a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
). In the same way,
dijoins (sets of edges that include an edge from each directed cut) are dual to
feedback arc set
In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks al ...
s (sets of edges that include an edge from each cycle).
Spanning trees
![Circularmazeexample](https://upload.wikimedia.org/wikipedia/commons/d/d2/Circularmazeexample.jpg)
A
spanning tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
may be defined as a set of edges that, together with all of the vertices of the graph, forms a connected and acyclic subgraph. But, by cut-cycle duality, if a set of edges in a planar graph is acyclic (has no cycles), then the set of edges dual to has no cuts, from which it follows that the complementary set of dual edges (the duals of the edges that are not in ) forms a connected subgraph. Symmetrically, if is connected, then the edges dual to the complement of form an acyclic subgraph. Therefore, when has both properties – it is connected and acyclic – the same is true for the complementary set in the dual graph. That is, each spanning tree of is complementary to a spanning tree of the dual graph, and vice versa. Thus, the edges of any planar graph and its dual can together be partitioned (in multiple different ways) into two spanning trees, one in the primal and one in the dual, that together extend to all the vertices and faces of the graph but never cross each other. In particular, the
minimum spanning tree
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. T ...
of is complementary to the maximum spanning tree of the dual graph. However, this does not work for
shortest path trees, even approximately: there exist planar graphs such that, for every pair of a spanning tree in the graph and a complementary spanning tree in the dual graph, at least one of the two trees has distances that are significantly longer than the distances in its graph.
An example of this type of decomposition into interdigitating trees can be seen in some simple types of
maze
A maze is a path or collection of paths, typically from an entrance to a goal. The word is used to refer both to branching tour puzzles through which the solver must find a route, and to simpler non-branching ("unicursal") patterns that lea ...
s, with a single entrance and no disconnected components of its walls. In this case both the maze walls and the space between the walls take the form of a mathematical tree. If the free space of the maze is partitioned into simple cells (such as the squares of a grid) then this system of cells can be viewed as an embedding of a planar graph, in which the tree structure of the walls forms a spanning tree of the graph and the tree structure of the free space forms a spanning tree of the dual graph. Similar pairs of interdigitating trees can also be seen in the tree-shaped pattern of streams and rivers within a
drainage basin
A drainage basin is an area of land where all flowing surface water converges to a single point, such as a river mouth, or flows into another body of water, such as a lake or ocean. A basin is separated from adjacent basins by a perimeter, t ...
and the dual tree-shaped pattern of ridgelines separating the streams.
This partition of the edges and their duals into two trees leads to a simple proof of
Euler’s formula for planar graphs with vertices, edges, and faces. Any spanning tree and its complementary dual spanning tree partition the edges into two subsets of and 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
Duncan MacLaren Young Sommerville (1879–1934) was a Scottish mathematician and astronomer. He compiled a bibliography on non-Euclidean geometry and also wrote a leading textbook in that field. He also wrote ''Introduction to the Geometry of N ...
, this proof of Euler's formula is due to
K. G. C. Von Staudt’s ''Geometrie der Lage'' (Nürnberg, 1847).
In nonplanar surface embeddings the set of dual edges complementary to a spanning tree is not a dual spanning tree. Instead this set of edges is the union of a dual spanning tree with a small set of extra edges whose number is determined by the genus of the surface on which the graph is embedded. The extra edges, in combination with paths in the spanning trees, can be used to
generate the
fundamental group
In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of ...
of the surface.
Additional properties
Any counting formula involving vertices and faces that is valid for all planar graphs may be transformed by planar duality into an equivalent formula in which the roles of the vertices and faces have been swapped. Euler's formula, which is self-dual, is one example. Another given by
Harary involves the
handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. In more colloquial terms, in a party of people some of whom ...
, according to which the sum of the
degrees of the vertices of any graph equals twice the number of edges. In its dual form, this lemma states that in a plane graph, the sum of the numbers of sides of the faces of the graph equals twice the number of edges.
The
medial graph
In the mathematical discipline of graph theory, the medial graph of plane graph ''G'' is another graph ''M(G)'' that represents the adjacencies between edges in the faces of ''G''. Medial graphs were introduced in 1922 by Ernst Steinitz to study ...
of a plane graph is
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
to the medial graph of its dual. Two planar graphs can have isomorphic medial graphs only if they are dual to each other.
A planar graph with four or more vertices is maximal (no more edges can be added while preserving planarity) if and only if its dual graph is both 3-vertex-connected and
3-regular.
A connected planar graph is
Eulerian (has even degree at every vertex) if and only if its dual graph is
bipartite.
A
Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
in a planar graph corresponds to a partition of the vertices of the dual graph into two subsets (the interior and exterior of the cycle) whose
induced subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.
Defini ...
s are both trees. In particular,
Barnette's conjecture
Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that eve ...
on the Hamiltonicity of cubic bipartite polyhedral graphs is equivalent to the conjecture that every Eulerian maximal planar graph can be partitioned into two induced trees.
If a planar graph has Tutte polynomial , then the Tutte polynomial of its dual graph is obtained by swapping and . For this reason, if some particular value of the Tutte polynomial provides information about certain types of structures in , then swapping the arguments to the Tutte polynomial will give the corresponding information for the dual structures. For instance, the number of strong orientations is and the number of acyclic orientations is . For bridge (graph theory), bridgeless planar graphs, graph colorings with colors correspond to nowhere-zero flows modulo on the dual graph. For instance, the four color theorem (the existence of a 4-coloring for every planar graph) can be expressed equivalently as stating that the dual of every bridgeless planar graph has a nowhere-zero 4-flow. The number of -colorings is counted (up to an easily computed factor) by the Tutte polynomial value and dually the number of nowhere-zero -flows is counted by .
An st-planar graph, ''st''-planar graph is a connected planar graph together with a bipolar orientation of that graph, an orientation that makes it acyclic with a single source and a single sink, both of which are required to be on the same face as each other. Such a graph may be made into a strongly connected graph by adding one more edge, from the sink back to the source, through the outer face. The dual of this augmented planar graph is itself the augmentation of another ''st''-planar graph.
Variations
Directed graphs
In a directed graph, directed plane graph, the dual graph may be made directed as well, by orienting each dual edge by a 90° clockwise turn from the corresponding primal edge.
[.] Strictly speaking, this construction is not a duality of directed planar graphs, because starting from a graph and taking the dual twice does not return to itself, but instead constructs a graph isomorphic to the transpose graph of , the graph formed from by reversing all of its edges. Taking the dual four times returns to the original graph.
Weak dual
The weak dual of a
plane graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cros ...
is the Glossary of graph theory#Subgraphs, subgraph of the dual graph whose vertices correspond to the bounded faces of the primal graph. A plane graph is outerplanar graph, outerplanar if and only if its weak dual is a tree (graph theory), forest. For any plane graph , let be the plane multigraph formed by adding a single new vertex in the unbounded face of , and connecting to each vertex of the outer face (multiple times, if a vertex appears multiple times on the boundary of the outer face); then, is the weak dual of the (plane) dual of .
Infinite graphs and tessellations
The concept of duality applies as well to infinite graphs embedded in the plane as it does to finite graphs. However, care is needed to avoid topological complications such as points of the plane that are neither part of an open region disjoint from the graph nor part of an edge or vertex of the graph. 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. Planar duality gives rise to the notion of a
dual tessellation
In geometry, every polyhedron is associated with a second dual structure, where the Vertex (geometry), vertices of one correspond to the Face (geometry), faces of the other, and the edges between pairs of vertices of one correspond to the edges b ...
, a tessellation formed by placing a vertex at the center of each tile and connecting the centers of adjacent tiles.
![Delaunay Voronoi](https://upload.wikimedia.org/wikipedia/commons/5/56/Delaunay_Voronoi.svg)
The concept of a dual tessellation can also be applied to partitions of the plane into finitely many regions. It is closely related to but not quite the same as planar graph duality in this case. For instance, the Voronoi diagram of a finite set of point sites is a partition of the plane into polygons within which one site is closer than any other. 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. The dual of this diagram is the Delaunay triangulation of the input, a planar graph that connects two sites by an edge whenever there exists a circle that contains those two sites and no other sites. The edges of the convex hull of the input are also edges of the Delaunay triangulation, but they correspond to rays rather than line segments of the Voronoi diagram. This duality between Voronoi diagrams and Delaunay triangulations can be turned into a duality between finite graphs in either of two ways: by adding an artificial vertex point at infinity, at infinity to the Voronoi diagram, to serve as the other endpoint for all of its rays, or by treating the bounded part of the Voronoi diagram as the weak dual of the Delaunay triangulation. Although the Voronoi diagram and Delaunay triangulation are dual, their embedding in the plane may have additional crossings beyond the crossings of dual pairs of edges. Each vertex of the Delaunay triangle is positioned within its corresponding face of the Voronoi diagram. Each vertex of the Voronoi diagram is positioned at the circumcenter of the corresponding triangle of the Delaunay triangulation, but this point may lie outside its triangle.
Nonplanar embeddings
The concept of duality can be extended to graph embeddings on two-dimensional manifolds other than the plane. The definition is the same: there is a dual vertex for each Connected space, connected component of the Complement (set theory), complement of the graph in the manifold, and a dual edge for each graph edge connecting the two dual vertices on either side of the edge. In most applications of this concept, it is restricted to embeddings with the property that each face is a topological disk; this constraint generalizes the requirement for planar graphs that the graph be connected. With this constraint, the dual of any surface-embedded graph has a natural embedding on the same surface, such that the dual of the dual is isomorphic to and isomorphically embedded to the original graph. For instance, the complete graph is a toroidal graph: it is not planar but can be embedded in a torus, with each face of the embedding being a triangle. This embedding has the Heawood graph as its dual graph.
[.]
The same concept works equally well for Orientability, non-orientable surfaces. For instance, can be embedded in the projective plane with ten triangular faces as the hemi-icosahedron, whose dual is the Petersen graph embedded as the hemi-dodecahedron.
Even planar graphs may have nonplanar embeddings, with duals derived from those embeddings that differ from their planar duals. For instance, the four Petrie polygons of a cube (hexagons formed by removing two opposite vertices of the cube) form the hexagonal faces of an embedding of the cube in a torus. The dual graph of this embedding has four vertices forming a complete graph with doubled edges. In the torus embedding of this dual graph, the six edges incident to each vertex, in cyclic order around that vertex, cycle twice through the three other vertices. In contrast to the situation in the plane, this embedding of the cube and its dual is not unique; the cube graph has several other torus embeddings, with different duals.
Many of the equivalences between primal and dual graph properties of planar graphs fail to generalize to nonplanar duals, or require additional care in their generalization.
Another operation on surface-embedded graphs is the Petrie dual, which uses the Petrie polygons of the embedding as the faces of a new embedding. Unlike the usual dual graph, it has the same vertices as the original graph, but generally lies on a different surface.
Surface duality and Petrie duality are two of the six Wilson operations, and together generate the group of these operations.
Matroids and algebraic duals
An algebraic dual of a connected graph is a graph such that and have the same set of edges, any Cycle space, cycle of is a Cut (graph theory), cut of , and any cut of is a cycle of . Every planar graph has an algebraic dual, which is in general not unique (any dual defined by a plane embedding will do). The converse is actually true, as settled by
Hassler Whitney
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...
in Whitney's planarity criterion:
: A connected graph is planar if and only if it has an algebraic dual.
The same fact can be expressed in the theory of matroids. If is the graphic matroid of a graph , then a graph is an algebraic dual of if and only if the graphic matroid of is the
dual matroid
In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it...
Matroid duals go back to the original paper by Hassler ...
of . Then Whitney's planarity criterion can be rephrased as stating that the
dual matroid
In matroid theory, the dual of a matroid M is another matroid M^\ast that has the same elements as M, and in which a set is independent if and only if M has a basis set disjoint from it...
Matroid duals go back to the original paper by Hassler ...
of a graphic matroid is itself a graphic matroid if and only if the underlying graph of is planar. If is planar, the dual matroid is the graphic matroid of the dual graph of . In particular, all dual graphs, for all the different planar embeddings of , have isomorphic graphic matroids.
For nonplanar surface embeddings, unlike planar duals, the dual graph is not generally an algebraic dual of the primal graph. And for a non-planar graph , the dual matroid of the graphic matroid of is not itself a graphic matroid. However, it is still a matroid whose circuits correspond to the cuts in , and in this sense can be thought of as a combinatorially generalized algebraic dual of .
The duality between Eulerian and bipartite planar graphs can be extended to binary matroids (which include the graphic matroids derived from planar graphs): a binary matroid is Eulerian matroid, Eulerian if and only if its dual matroid is bipartite matroid, bipartite.
[.]
The two dual concepts of girth and edge connectivity are unified in matroid theory by matroid girth: the girth of the graphic matroid of a planar graph is the same as the graph's girth, and the girth of the dual matroid (the graphic matroid of the dual graph) is the edge connectivity of the graph.
[.]
Applications
Along with its use in graph theory, the duality of planar graphs has applications in several other areas of mathematical and computational study.
In geographic information systems, flow networks (such as the networks showing how water flows in a system of streams and rivers) are dual to cellular networks describing drainage divides. 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.
In
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the hum ...
, digital images are partitioned into small square pixels, each of which has its own color. The dual graph of this subdivision into squares has a vertex per pixel and an edge between pairs of pixels that share an edge; it is useful for applications including clustering of pixels into connected regions of similar colors.
In
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
, the duality between Voronoi diagrams and Delaunay triangulations implies that any
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
for constructing a Voronoi diagram can be immediately converted into an algorithm for the Delaunay triangulation, and vice versa. The same duality can also be used in finite element method, finite element
mesh generation
Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells.
Often these cells form a simplicial complex.
Usually the cells partition the geometric input domain. ...
. 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.
In the Logic synthesis, synthesis of CMOS circuits, the function to be synthesized is represented as a formula in Boolean algebra. Then this formula is translated into two series–parallel graph, series–parallel multigraphs. These graphs can be interpreted as circuit diagrams in which the edges of the graphs represent transistors, gated by the inputs to the function. One circuit computes the function itself, and the other computes its complement. 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. These two circuits, augmented by an additional edge connecting the input of each circuit to its output, are planar dual graphs.
History
The duality of convex polyhedra was recognized by Johannes Kepler in his 1619 book ''Harmonices Mundi''.
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''. This was even before Leonhard Euler's 1736 work on the Seven Bridges of Königsberg that is often taken to be the first work on
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
. Varignon analyzed the forces on static systems of struts by drawing a graph dual to the struts, with edge lengths proportional to the forces on the struts; this dual graph is a type of Cremona diagram. 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 in 1891. Duality as an operation on abstract planar graphs was introduced by
Hassler Whitney
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...
in 1931.
[.]
Notes
External links
*
{{DEFAULTSORT:Dual Graph
Algebraic graph theory
Topological graph theory
Planar graphs
Duality theories, Graph
Graph operations
de:Dualität (Mathematik)#Geometrisch dualer Graph