G′is the dual graph of G

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). Image File history File links Dualgraphs. ... Image File history File links Dualgraphs. ... In mathematics and computer science, graph theory studies the properties of graphs. ... In graph theory, a planar graph is a graph that can be embedded in the plane so that no edges intersect. ... In mathematics, an embedding (or imbedding) is one instance of some mathematical object contained within another instance, such as a group that is a subgroup. ... Two intersecting planes in R3 In mathematics, a plane is a fundamental two-dimensional object. ... This article just presents the basic definitions. ... This article just presents the basic definitions. ...

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′

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 (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. Image File history File links Nonisomorphicdualgraps. ... Image File history File links Nonisomorphicdualgraps. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of interesting mapping between objects. ... In algebraic topology, the Euler characteristic is a topological invariant (in fact, homotopy invariant) defined for a broad class of topological spaces. ... This article is about the geometric shape. ...

Algebraic dual

Let G be a connected graph. An algebraic dual of G is a graph so that G and have the same set of edges, any cycle of G is a cut of and any cut of G is a cycle of . 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: // The binary cycle space In graph theory, certain vector spaces over the two-element field Z2 are associated with an undirected graph; this allows one to use the tools of linear algebra to study graphs. ...

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

References

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