25210 Planar GraphsFig.10.9.ThedoftheplanegraphofFigure10.7Proof Let G be a loopless 3-conected plane graph and let u be a vertex of G.Then G - u is nonseparable, so each face of G - u is bounded by a cycle, byTheorem 10.7. If f is the face of G - u in which the vertex v was situated, theneighbours of u lie on its bounding cycle o(f)口DUALSGiven a plane graph G, one can define a second graph G* as follows. CorrespondingtoeachfacefofGtherea vertex f* of G*,and corresponding to each edge e oGthere is an edge e*of G*.Two vertices f* and qare joined by the edge e*in Gif and onlyif their corresponding faces f and g are separated by the edge ein GObserervethata cut edge of G, then f*isaloopofG*converselysoeif e is a loop of G, the edge e+ is a cut edge of G*. The graph G* is called the dualof G. The dual of the plane graph of Figure 10.7 is drawn in Figure 10.9.In the dual G* of a plane graph G, the edges corresponding to those which liein the boundary of a face f of G are just the edges incident with the correspondingvertex f*. When G has no cut edges, G* has no loops, and this set is precisely thetrivial edge cut o(f*):that is.a(f*) = [et :eE0(f))It is for this reason that the notation a(f) was choserIt is easy to see that the dual G* of a plane graph G isitself a planar graphin fact, there is a natural embedding of G* in the plane. We place each vertex f*in thecorrespondingfacef of G,and thendraw eachedgee* insuchawaythatit crosses thecorresponding edee eof Gexactly once (and crosses no other edgeof G). This procedure is illustrated in Figure 10.10, where the dual is indicated byheavylinIt is intuitively clear that we can always draw thedual as a plane graph in thisway, but we do not prove this fact. We refer to such a drawing of the dual as aplane dual of the plane graph G.252 10 Planar Graphs e∗ 1 e∗ 2 e∗ 3 e∗ 4 e∗ 5 e∗ 6 e∗ 7 e∗ 8 e∗ 9 e∗ 10 f ∗ 1 f ∗ 2 f ∗ 3 f ∗ 4 f ∗ 5 Fig. 10.9. The dual of the plane graph of Figure 10.7 Proof Let G be a loopless 3-connected plane graph and let v be a vertex of G. Then G − v is nonseparable, so each face of G − v is bounded by a cycle, by Theorem 10.7. If f is the face of G − v in which the vertex v was situated, the neighbours of v lie on its bounding cycle ∂(f).
Duals Given a plane graph G, one can define a second graph G∗ as follows. Corresponding to each face f of G there is a vertex f ∗ of G∗, and corresponding to each edge e of G there is an edge e∗ of G∗. Two vertices f ∗ and g∗ are joined by the edge e∗ in G∗ if and only if their corresponding faces f and g are separated by the edge e in G. Observe that if e is a cut edge of G, then f = g, so e∗ is a loop of G∗; conversely, if e is a loop of G, the edge e∗ is a cut edge of G∗. The graph G∗ is called the dual of G. The dual of the plane graph of Figure 10.7 is drawn in Figure 10.9. In the dual G∗ of a plane graph G, the edges corresponding to those which lie in the boundary of a face f of G are just the edges incident with the corresponding vertex f ∗. When G has no cut edges, G∗ has no loops, and this set is precisely the trivial edge cut ∂(f ∗); that is, ∂(f ∗) = {e∗ : e ∈ ∂(f)} It is for this reason that the notation ∂(f) was chosen. It is easy to see that the dual G∗ of a plane graph G is itself a planar graph; in fact, there is a natural embedding of G∗ in the plane. We place each vertex f ∗ in the corresponding face f of G, and then draw each edge e∗ in such a way that it crosses the corresponding edge e of G exactly once (and crosses no other edge of G). This procedure is illustrated in Figure 10.10, where the dual is indicated by heavy lines. It is intuitively clear that we can always draw the dual as a plane graph in this way, but we do not prove this fact. We refer to such a drawing of the dual as a plane dual of the plane graph G