Dual graph

Dual graph is a term used in the mathematical study of graphs. Let G be a connected planar graph with a particular embedding in the plane, in other words, drawn without edge intersections. A dual graph of G is a graph that has a vertex for each plane region, and an edge for each edge joining two neighboring regions (see diagram).

[edit]

Properties

The dual of a plane graph is always a plane graph.
Since dualizing graphs changes regions into vertices, vertices into regions, and edges into edges, it follows that if G′ is the dual of G then G is the dual of G′

Dual graphs are not unique, in the sense that a same graph can have non-isomorphic dual graphs (since the dual graph depends on a particular plane embedding). In the picture, G′ and G″ are not isomorphic because G′ has a vertex with order 7 (the outer region) but G″ doesn't (see diagram).

Because of the dualism, any result involving counting regions and vertices can be dualized exchanging them. Moreover, dualism is deeply related with the symmetric roll of faces and vertices of Euler's formula for polyhedra.

[edit]

Algebraic dual

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