25610 Planar GraphsthatGhas atleasttwo edges,hencenoloopsorcut edges.Let e be an edge of GThen either Ge or G /e is nonseparable (Exercise 5.3.2). If Gle is nonseparableso is (G |e)* G* /e*, by the induction hypothesis and Proposition 10.12. ApplyingExercise5.2.2b,we deduce that G*isnonseparable.ThecasewhereG/eisnonseparablecanbeestablished byananalogousargumentLThe dual of any plane graph is connected, and it follows from Theorem 10.14that the dual of a loopless 2-connected plane graph is 2-connected. Furthermore,one can show that the dual of a simple 3-connected plane graph is 3-connected(Exercise 10.2.7)The notion of plane duality can be extended to directed graphs. Let D beplane digraph, with underlying plane graph G. Consider a plane dual G* of G.Each arc a of D separates two faces of G. As a is traversed from its tail to itshead, one of these faces lies to the left of a and one to its right. We denote thesetwo faces by la and ra, respectively; note that if a is a cut edge, la = Ta. Foreach arc a of D,we now orientthe edgeof G*that crosses it as an arc a*bydesignating the end lying in l. as the tail of a* and the end lying in ra as its head.The resulting plane digraph D* is the directed plane dual of D. An example isshown in Figure10.13.Fig.10.13. An orientation of the triangular prism, and its directed plane dualVECTORSPACESANDDUALITYWe have seen that the cycle and bond spaces are orthogonal complements (Exer-cise 2.6.4a). In the case of plane graphs, this relationship of orthogonality can alsobe expressed in terms of duality, as we now explain. As usual in this context, weidentify cycles, trees, and cotrees with their edge setsWe observed earlier that all duals are connected (Proposition 10.9). A similarargument, based on the fact that the interior of a cycle in a plane graph is arcwiseonnected, establishes the following proposition.256 10 Planar Graphs that G has at least two edges, hence no loops or cut edges. Let e be an edge of G. Then either G\ e or G/e is nonseparable (Exercise 5.3.2). If G\ e is nonseparable, so is (G \ e)∗ ∼= G∗ /e∗, by the induction hypothesis and Proposition 10.12. Ap￾plying Exercise 5.2.2b, we deduce that G∗ is nonseparable. The case where G/e is nonseparable can be established by an analogous argument.
The dual of any plane graph is connected, and it follows from Theorem 10.14 that the dual of a loopless 2-connected plane graph is 2-connected. Furthermore, one can show that the dual of a simple 3-connected plane graph is 3-connected (Exercise 10.2.7). The notion of plane duality can be extended to directed graphs. Let D be a plane digraph, with underlying plane graph G. Consider a plane dual G∗ of G. Each arc a of D separates two faces of G. As a is traversed from its tail to its head, one of these faces lies to the left of a and one to its right. We denote these two faces by la and ra, respectively; note that if a is a cut edge, la = ra. For each arc a of D, we now orient the edge of G∗ that crosses it as an arc a∗ by designating the end lying in la as the tail of a∗ and the end lying in ra as its head. The resulting plane digraph D∗ is the directed plane dual of D. An example is shown in Figure 10.13. Fig. 10.13. An orientation of the triangular prism, and its directed plane dual Vector Spaces and Duality We have seen that the cycle and bond spaces are orthogonal complements (Exer￾cise 2.6.4a). In the case of plane graphs, this relationship of orthogonality can also be expressed in terms of duality, as we now explain. As usual in this context, we identify cycles, trees, and cotrees with their edge sets. We observed earlier that all duals are connected (Proposition 10.9). A similar argument, based on the fact that the interior of a cycle in a plane graph is arcwise￾connected, establishes the following proposition