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 are250 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