Dual Of A Planer Graph

DUAL OF A PLANAR GRAPH: Consider the plane representation of a graph in Figure (2.60)(a) with six regions of faces F1, F2, F3, F4, F5 and F6.
Let us place six points P1, P2, ...... P6, one in each of the regions, as shown in Figure (2.60)(b). Next let us join these six points according to the following procedure :

1. If two regions Fi and Fj are adjacent (i.e., have a common edge), draw a line joining points Pi and Pj that intersects the common edge between Fi and Fj exactly once.
2. If there is more than one edge common between Fi and Fj, draw one line between points Pi and Pj for each of the common edges.
3. For an edge e lying entirely in one region, say Fk, draw a self-loop at point Pk intersecting e exactly once.

By this procedure we obtained a new graph G* (in broken lines in Figure (2.60)(c) consisting of six vertices, P1, P2, ...... P6 and of edges joining these vertices. Such a graph G* is called dual (a geometrical dual) of G Clearly, there is a one-to-one correspondence between the edges of graph G and its dual G*— one edge of G* intersecting one edge of G. Some simple observations that can be made about the relationship between a planar graph G and its dual G* are :

(i) An edge forming a self-loop in G yields a pendant edge in G*.
(ii) A pendant edge in G yields a self-loop in G*.
(iii) Edges that are in series in G produce parallel edges in G*.
(iv) Parallel edges in G produce edges in series in G*.
(v) Remarks (i)-(iv) are the result of the general observation that the number of edges constituting the boundary of a region Fi in G is equal to the degree of the corresponding vertex Pi in G*.
(vi) Graph G* is also embedded in the plane and is therefore planar.
(vii) Considering the process of drawing a dual G* from G, it is evident that G is a dual of G* (see Fig. (2.60) (c)). Therefore, instead of calling G* a dual of G, we usually say that G and G* are dual graphs.
(viii) If n, e, f, r and μ denote as usual the numbers of vertices, edges, regions, rank, and nullity of a connected planar graph G, and if n*, e*, f*, r* and μ* are the corresponding numbers in dual graph G*, then
n* = f, e* = e, f* = n.

Using the above relationship, one can immediately get r* = μ, μ* = r.

Uniqueness of the dual: Given a planar graph G, we can construct more than one geometric dual of G. All the duals so constructed have one important property. This property is stated in the following result : All geometric duals of a planar graph G are 2-isomorphic, and every graph 2-isomorphic to a geometric dual of G is also a geometric dual of G.

Double dual: Given a planar graph G, suppose we construct its geometric dual G* and the geometric dual G** of G*.
Then G** is called a double geometric dual of G. If G is a planar graph, then G** and G are 2-isomorphic.

Self-dual graphs: A planar graph G is said to be self-dual if G is isomorphic to its geometric dual G*, i.e., if
G ≈ G*.
Consider the complete graph K4 of four vertices show in Figure (2.61)(a). Its geometric dual K4* can be constructed. This is shown in Figure (2.61)(b).