Dual graph

From Wikipedia, the free encyclopedia

G′ is the dual graph of G

In mathematics, a dual graph of a given planar graph G has a vertex for each plane region of G, and an edge for each edge joining two neighboring regions. The term "dual" is used because this property is symmetric, meaning that if G is a dual of H, then H is a dual of G; in effect, these graphs come in pairs.

1 Properties
2 Algebraic dual
3 Notes
4 References

[edit] Properties

The dual of a plane graph is a plane graph (which may have loops and multiple edges ^[1]).
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.

Dual graphs are not unique, in the sense that a same graph can have non-isomorphic dual graphs because the dual graph depends on a particular plane embedding. 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.

[edit] Algebraic dual

Let G be a connected graph. An algebraic dual of G is a graph $G^\star$ so that G and $G^\star$ have the same set of edges, any cycle of G is a cut of $G^\star$ and any cut of G is a cycle of $G^\star$ . 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: