dual graph


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.

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.

Algebraic dual

Let G be a connected graph. An algebraic dual of G is a graph G^★ so thatG 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:

Notes

References

• H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.
• {{mathworld | urlname = DualGraph | title = Dual graph}}
• {{mathworld | urlname = Self-DualGraph | title = Self-dual graph}}

Duální grafGrafo dualGraphe dualGraf dualnyDual Graph is also used in the Mesh Partitioning issue.

(...as imported from WP)

home | about | policy | newsfeed