G′ is the dual graph of G

In mathematics, a dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden In Topological graph theory, an embedding of a graph G on a Surface &Sigma is a representation of G on &Sigma in which points The term "dual" is used because this property is symmetric, meaning that if H is a dual of G, then G is a dual of H (if G is connected). In Mathematics, duality has numerous meanings Generally speaking duality is a metamathematical involution. In Mathematics, the term "symmetric function" can mean two different things The same notation of duality may also be used for more general embeddings of graphs on manifolds. A manifold is a mathematical space in which every point has a neighborhood which resembles Euclidean space, but in which the global structure may be

Properties

• The dual of a plane graph is a plane graph (which may have loops and multiple edges ^[1]). Kuratowski's and Wagner's theorems The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of Forbidden
• If G is a connected graph and if G′ is a dual of G then G is a dual of G′.

G′ and G″ are duals for G, but they are not isomorphic. In Graph theory, an isomorphism of graphs G and H is a Bijection between the vertex sets of G and H

• Dual graphs are not unique, in the sense that the same graph can have non-isomorphic dual graphs because the dual graph depends on a particular plane embedding. In Graph theory, an isomorphism of graphs G and H is a Bijection between the vertex sets of G and H In the picture, G′ and G″ are not isomorphic because G′ has a vertex with degree 6 (the outer region) but G″ doesn't (see diagram).

Because of the dualism, any result involving counting regions and vertices can be dualized by exchanging them.

Algebraic dual

Let G be a connected graph. An algebraic dual of G is a graph G^★ so that G and G^★ have the same set of edges, any cycle of G is a cut of G^★, and any cut of G is a cycle of G^★. The binary cycle space In Graph theory, certain Vector spaces over the two-element field Z 2 are associated with an undirected 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 Whitney:

A connected graph G is planar if and only if it has an algebraic dual.

Notes

References

• H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.

Dual Graph is also used in the Mesh Partitioning issue.