25010 Planar GraphsThe boundary of a face f is the boundary of the open set f in the usualtopological sense. A face is said to be incident with the vertices and edges in itsboundary, and two faces are adjacent if their boundaries have an edge in common.In Figure 10.7, the face fi is incident with the vertices 1, V2, v3, U4, s and the: it is adjacent to the faces f3, fa,fs.edgese1.eo.Wedenotethe boundaryofafacefby(f)Therationaleforthisnotationbecomes apparent shortly, when we discuss duality. The boundary of a face maybe regarded as a subgraph. Moreover, when there is no scope for confusion, we usethenotation (f) todenote the edge set of this subgraph.Proposition i0.5 Let G be a planar graph, and let f be a face in some planarembedding of G.Then G admits a planar embedding whose outer face has the sameboundary as f.Proof Consider an embedding G of G on the sphere; such an embedding existsby virtue of Theorem 10.4.Denote by f the face of G corresponding to f. Let z bea point in the interior of f, and let (G) be the image of G under stereographicprojection from z. Clearly (G) is a planar embedding of G with the desiredproperty.口By the Jordan Curve Theorem, a planar embedding of a cycle has exactlytwo faces.In theensuing discussion ofplanegraphs,weassume,without proof,anumberof otherintuitivelyobvious statements concerningtheirfaces.Weassurfor example, that a planar embedding of a tree has just one face, and that eachfaceboundaryina connected plane graph is itself connected. Soneofthesefactsrelyon another basicresultof planetopology,known as the JordanSchonfiessTheorem.Theorem 10.6THE JORDAN-SCHONFLIESS THEOREMAny homeomorphism of a simple closed curve in the plane onto another simpleclosed curve can be ertended to a homeomorphism of the planeOne implication ofthis theorem isthat any point pon asimpleclosed curveCcan be connected to any point not on C by means of a simcurvewhichmeetsConly in p. We refer the reader to Mohar and Thomassen (2001) for further details.A cut edge in a plane graph has just one incident face, but we may think of theedgeas being incident twice withthesameface (oncefrom each side);alotheredges are incident with two distinct faces. We say that an edge separates the facesincident with it. The degree, d(f), of a face f is the number of edges in its boundarya(f), cut edges being counted twice. In Figure 10.7, the edge eg separates the facesf2 and f3 and the edge es separates the face fs from itself; the degrees of f3 andfs are6 and 5,respectivelySuppose that G is a connected plane graph. To subdivide a face f of G is toadd a new edge e joining two vertices on its boundary in such a way that, apartfrom its endpooints, e lies entirely in the interior of f. This operation results inplane graph G + e with exactly one more face than G; all faces of G except f are
250 10 Planar Graphs The boundary of a face f is the boundary of the open set f in the usual topological sense. A face is said to be incident with the vertices and edges in its boundary, and two faces are adjacent if their boundaries have an edge in common. In Figure 10.7, the face f1 is incident with the vertices v1,v2,v3,v4,v5 and the edges e1,e2,e3,e4,e5; it is adjacent to the faces f3,f4,f5. We denote the boundary of a face f by ∂(f). The rationale for this notation becomes apparent shortly, when we discuss duality. The boundary of a face may be regarded as a subgraph. Moreover, when there is no scope for confusion, we use the notation ∂(f) to denote the edge set of this subgraph. Proposition 10.5 Let G be a planar graph, and let f be a face in some planar embedding of G. Then G admits a planar embedding whose outer face has the same boundary as f. Proof Consider an embedding G of G on the sphere; such an embedding exists by virtue of Theorem 10.4. Denote by f the face of G corresponding to f. Let z be a point in the interior of f , and let π(G) be the image of G under stereographic projection from z. Clearly π(G) is a planar embedding of G with the desired property. By the Jordan Curve Theorem, a planar embedding of a cycle has exactly two faces. In the ensuing discussion of plane graphs, we assume, without proof, a number of other intuitively obvious statements concerning their faces. We assume, for example, that a planar embedding of a tree has just one face, and that each face boundary in a connected plane graph is itself connected. Some of these facts rely on another basic result of plane topology, known as the Jordan–Sch¨onfliess Theorem. Theorem 10.6 The Jordan–Schonfliess Theorem ¨ Any homeomorphism of a simple closed curve in the plane onto another simple closed curve can be extended to a homeomorphism of the plane. One implication of this theorem is that any point p on a simple closed curve C can be connected to any point not on C by means of a simple curve which meets C only in p. We refer the reader to Mohar and Thomassen (2001) for further details. A cut edge in a plane graph has just one incident face, but we may think of the edge as being incident twice with the same face (once from each side); all other edges are incident with two distinct faces. We say that an edge separates the faces incident with it. The degree, d(f), of a face f is the number of edges in its boundary ∂(f), cut edges being counted twice. In Figure 10.7, the edge e9 separates the faces f2 and f3 and the edge e8 separates the face f5 from itself; the degrees of f3 and f5 are 6 and 5, respectively. Suppose that G is a connected plane graph. To subdivide a face f of G is to add a new edge e joining two vertices on its boundary in such a way that, apart from its endpoints, e lies entirely in the interior of f. This operation results in a plane graph G + e with exactly one more face than G; all faces of G except f are
10.2Duality251Fig.10.8. Subdivision of a face f by an edge alsofacesofG+eand thefaceisreplacedbytwonewfaces,fiand f2whichmeet in the edge e, as illustrated in Figure 10.8.In a connected plane graph the boundary of a face can be regarded as a closedwalk in which each cut edge of the graph that lies in the boundary is traversedtwice. This is clearly so for plane trees, and can be established in general by induction on the number of faces (Exercise 10.2.2.) In the plane graph of Figure 10.7,forinstancea(f3)=Vieivae2uge1ose7ueeeieguiand a(fs)=ieeugeguege7vsegu1Moreover, in the case of nonseparable graphs, these boundary walks are simplycycles, as was shown by Whitney (1932c)Theorem 10.7In a nonseparable plane graph other than Ki or K2,each face isbounded by a cycle.ProoLet G bonseparable plane graph. Consider an ear deccDositioGo.Gr...,Gk of G, where Gg is a cycle, Gk = G, and, for 0<i≤ k -2,Gi+1:=G,UP, is a nonseparable plane subgraph of G, where P, is an ear of GSince Go is a cycle, the two faces of Go are clearly bounded by cycles. Assume.inductively, that all faces of G, are bounded by cycles, where i ≥0. Because Gi+isaplanegraph,theear P,of Gis contained in somefacef of Gi.(MorepreciselyGi+i is obtained from G, by subdividing the face f by an edge joining the endsof P, and then subdividing that edge by inserting the internal vertices of P.)Each face of Giother than f is aface of Gi+t as well,and so, by the inductiohypothesis, is bounded by a cycle. On the other hand, the face f of G, is dividedbyinowofasofGndisasyoseethatthee,ooarebounddy口cyclesOne consequence of Theorem 10.7 is that all planar graphs without cut edgeshave cycle double covers (Exercise 10.2.8). Another is the following.Corollary 10.8 In a loopless 3-connected plane graph, the neighbours of any verter lie on a common cycle
10.2 Duality 251 f f1 f2 e Fig. 10.8. Subdivision of a face f by an edge e also faces of G + e, and the face f is replaced by two new faces, f1 and f2, which meet in the edge e, as illustrated in Figure 10.8. In a connected plane graph the boundary of a face can be regarded as a closed walk in which each cut edge of the graph that lies in the boundary is traversed twice. This is clearly so for plane trees, and can be established in general by induction on the number of faces (Exercise 10.2.2.) In the plane graph of Figure 10.7, for instance, ∂(f3) = v1e1v2e2v3e10v5e7v6e6v1e9v1 and ∂(f5) = v1e6v6e8v7e8v6e7v5e5v1 Moreover, in the case of nonseparable graphs, these boundary walks are simply cycles, as was shown by Whitney (1932c). Theorem 10.7 In a nonseparable plane graph other than K1 or K2, each face is bounded by a cycle. Proof Let G be a nonseparable plane graph. Consider an ear decomposition G0,G1,...,Gk of G, where G0 is a cycle, Gk = G, and, for 0 ≤ i ≤ k − 2, Gi+1 := Gi ∪ Pi is a nonseparable plane subgraph of G, where Pi is an ear of Gi. Since G0 is a cycle, the two faces of G0 are clearly bounded by cycles. Assume, inductively, that all faces of Gi are bounded by cycles, where i ≥ 0. Because Gi+1 is a plane graph, the ear Pi of Gi is contained in some face f of Gi. (More precisely, Gi+1 is obtained from Gi by subdividing the face f by an edge joining the ends of Pi and then subdividing that edge by inserting the internal vertices of Pi.) Each face of Gi other than f is a face of Gi+1 as well, and so, by the induction hypothesis, is bounded by a cycle. On the other hand, the face f of Gi is divided by Pi into two faces of Gi+1, and it is easy to see that these, too, are bounded by cycles. One consequence of Theorem 10.7 is that all planar graphs without cut edges have cycle double covers (Exercise 10.2.8). Another is the following. Corollary 10.8 In a loopless 3-connected plane graph, the neighbours of any vertex lie on a common cycle
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
10.2Duality253Fig.10.10.The plane graph of Figure10.7and its plane dualProposition 10.9 The dual of any plane graph is connected.Proof Let G be a plane graph and G* a plane dual of G. Consider any two verticesof G*.Thereis a curvein the plane connecting thennwhichavoidsall verticesofG. The sequence of faces and edges of G traversed by this curve corresponds in G*to a walk connecting the two vertices.口Although defined abstractly.it is often convenient to regard the dual G* of plane graph G as being itself a plane graph, embedded as described above. Onemaythen consider thedual**ofWhen Gisconnected, itisnot dificulttoprove that G** = G (Exercise 10.2.4); a glance at Figure 10.10 indicates why thisSSIt should be noted that isomorphic plane graphs may well have nonisomorphicduals. For example, although the plane graphs in Figure 10.1l are isomorphic, theirduals arenot:the:ohshowninFigure10.1lahastwofacesofdegreethDlanegrarwhereas that of Figure i0.ilb has only one such face. Thus the notion of a dualgraph is meaningful only for plane graphs, and not for planar graphs in generalWe show, however (in Theorem 10.28) that every simple 3-connected planar graphhas a unique planar embedding (in the sense that its face boundaries are uniquelydetermined) and hence has a unique dual.The following relations are direct consequences of the definition of the dual G*u(G*)=f(G), e(G*) = e(G), and dg-(f*)= dc(f) for all f e F(G) (10.1)The next theorem may be regarded as a dual version of Theorem 1.1.Theorem 10.10 If G is a plane graph,Z d(f) = 2mfEF
10.2 Duality 253 Fig. 10.10. The plane graph of Figure 10.7 and its plane dual Proposition 10.9 The dual of any plane graph is connected. Proof Let G be a plane graph and G∗ a plane dual of G. Consider any two vertices of G∗. There is a curve in the plane connecting them which avoids all vertices of G. The sequence of faces and edges of G traversed by this curve corresponds in G∗ to a walk connecting the two vertices. Although defined abstractly, it is often convenient to regard the dual G∗ of a plane graph G as being itself a plane graph, embedded as described above. One may then consider the dual G∗∗ of G∗. When G is connected, it is not difficult to prove that G∗∗ ∼= G (Exercise 10.2.4); a glance at Figure 10.10 indicates why this is so. It should be noted that isomorphic plane graphs may well have nonisomorphic duals. For example, although the plane graphs in Figure 10.11 are isomorphic, their duals are not: the plane graph shown in Figure 10.11a has two faces of degree three, whereas that of Figure 10.11b has only one such face. Thus the notion of a dual graph is meaningful only for plane graphs, and not for planar graphs in general. We show, however (in Theorem 10.28) that every simple 3-connected planar graph has a unique planar embedding (in the sense that its face boundaries are uniquely determined) and hence has a unique dual. The following relations are direct consequences of the definition of the dual G∗. v(G∗) = f(G), e(G∗) = e(G), and dG∗ (f ∗) = dG(f) for all f ∈ F(G) (10.1) The next theorem may be regarded as a dual version of Theorem 1.1. Theorem 10.10 If G is a plane graph, f∈F d(f)=2m
25410 Planar Graphs(a)(6)Fig. 10.11. Isomorphic plane graphs with nonisomorphic dualsProofLetG*bethedualofG.By(i0.1)andTheorem1.1 d(f)=1口d(f*) = 2e(G*) = 2e(G) = 2mfEF(G)f*EV(G*)A simple connected plane graph in which all faces have degree three is calleda plane triangulation or, for short, a triangulation. The tetrahedron, the octahe-dron, and the icosahedron (depicted in Figure 1.14) are all triangulations. As aconsequence of (10.1) we have:Proposition 10.11 A simple connected plane graph is a triangulation if and onlyif its dual is cubicIt is easy to show that every simple plane graph on three or more vertices is aspanning subgraph of a triangulation (Exercise 10.2.5). On the other hand, as weshow in Section 10.3, no simple spanning supergraph of a triangulation is planarFor this reason, triangulaticons are also known as marimal planar graphs. Theyplay an important role in the theory of planar graphs.DELETION-CONTRACTION DUALITYLet G be a planal graph and G a planembedding of G. Foredge e of Ga plane embedding of Gle can be obtained by simply deleting the line e fromG. Thus, the deletion of an edge from a planar graph results in a planar graph.Although less obvious,the contraction of an edge ofaplanargraphalsoresults ina planar graph (Exercise 10.1.4b). Indeed, given any edge e of a planar graph Gedding G of G, the line e of G can be contracted to a single pointandaplanai(and the lines incident to its ends redrawn) so that the resulting plane graph is anar embedding of G/e.planThe following two propositions show that the operations of contracting anddeleting edges in plane graphs are related in a natural way under duality.Proposition 10.12 Let G be a connected plane graph, and let e be an edge of Gthat is not a cut edge.Then(G le)*= G* /e*
254 10 Planar Graphs (a) (b) Fig. 10.11. Isomorphic plane graphs with nonisomorphic duals Proof Let G∗ be the dual of G. By (10.1) and Theorem 1.1, f∈F (G) d(f) = f ∗∈V (G∗) d(f ∗)=2e(G∗)=2e(G)=2m A simple connected plane graph in which all faces have degree three is called a plane triangulation or, for short, a triangulation. The tetrahedron, the octahedron, and the icosahedron (depicted in Figure 1.14) are all triangulations. As a consequence of (10.1) we have: Proposition 10.11 A simple connected plane graph is a triangulation if and only if its dual is cubic. It is easy to show that every simple plane graph on three or more vertices is a spanning subgraph of a triangulation (Exercise 10.2.5). On the other hand, as we show in Section 10.3, no simple spanning supergraph of a triangulation is planar. For this reason, triangulations are also known as maximal planar graphs. They play an important role in the theory of planar graphs. Deletion–Contraction Duality Let G be a planar graph and G a plane embedding of G. For any edge e of G, a plane embedding of G \ e can be obtained by simply deleting the line e from G. Thus, the deletion of an edge from a planar graph results in a planar graph. Although less obvious, the contraction of an edge of a planar graph also results in a planar graph (Exercise 10.1.4b). Indeed, given any edge e of a planar graph G and a planar embedding G of G, the line e of G can be contracted to a single point (and the lines incident to its ends redrawn) so that the resulting plane graph is a planar embedding of G/e. The following two propositions show that the operations of contracting and deleting edges in plane graphs are related in a natural way under duality. Proposition 10.12 Let G be a connected plane graph, and let e be an edge of G that is not a cut edge. Then (G \ e) ∗ ∼= G∗ /e∗