Dual graph

From Wikipedia, the free encyclopedia

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. 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). The same notation of duality may also be used for more general embeddings of graphs on manifolds.

Contents 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′.

• 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 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^★ 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^★. 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.

[edit] Notes

[edit] 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.