10.1 Plane and Planar Graphs245Theorem 10.1 THE JORDAN CURVE THEOREMAny simple closed curve C in the plane partitions the rest of the plane into tudisjoint arcwise-connected open sets.Although this theorem is intuitively obvious, giving a formal proof of it is quitetricky.Thetwo open sets into which ae closed curve Cpartitions theplanor and the erterior of C. We denote them by int(C) and ext(C),arecalled the interand their closures by Int(C) and Ext(C), respectively (thus Int(C) n Ext(C) = C)The Jordan Curve Theorem implies that every arc joining a point of int(C) to apoint of ext(C) meets C in at least one point (see Figure 10.2)teext(C)Fig.10.2.The Jordan Curve TheoremFigurebshowsthat thegraph Keisplanar.ThegraphKs,ontheothehand, is not planar. Let us see how the Jordan Curve Theorem can be used todemonstrate this fact.Theorem 10.2 K, is nonplanar.Proof By contradiction. Let G be a planar embedding of Ks, with verticesA.Us.BecauseGiscomplete.anytwo ofitsverticeare joined by an..edge.Nowthecycle=uaisasimplecosed curveitheplane,andthevertex u4 must lie either in int(C) or in ext(C). Without loss of generality, we maysuppose that u4 E int(C). Then the edges vi4, v2u4, v3v4 all lie entirely in int(C),too (apart from their ends V1, V2, v3) (see Figure 10.3).Consider the cycles Ci = v2v3va2,C2:Vi4U3, and C3=iu2U4ui.Observe that v; e ext(C), i = 1,2,3. Because v,us e E(G) and G is a planegraph, it follows fromthe Jordan Curve Theorem that us E ext(C), i = 1,2,3,too. Thus us E ext(C). But now the edge uaus crosses C, again by the JordanCurve Theorem. This contradicts the planarity of the embedding G.口A similar argument can be used toestablish that K3,s is nonplanar, too (Exercise 10.1.1b)
10.1 Plane and Planar Graphs 245 Theorem 10.1 The Jordan Curve Theorem Any simple closed curve C in the plane partitions the rest of the plane into two disjoint arcwise-connected open sets. Although this theorem is intuitively obvious, giving a formal proof of it is quite tricky. The two open sets into which a simple closed curve C partitions the plane are called the interior and the exterior of C. We denote them by int(C) and ext(C), and their closures by Int(C) and Ext(C), respectively (thus Int(C) ∩ Ext(C) = C). The Jordan Curve Theorem implies that every arc joining a point of int(C) to a point of ext(C) meets C in at least one point (see Figure 10.2). C int(C) ext(C) Fig. 10.2. The Jordan Curve Theorem Figure 10.1b shows that the graph K5 \e is planar. The graph K5, on the other hand, is not planar. Let us see how the Jordan Curve Theorem can be used to demonstrate this fact. Theorem 10.2 K5 is nonplanar. Proof By contradiction. Let G be a planar embedding of K5, with vertices v1,v2,v3,v4,v5. Because G is complete, any two of its vertices are joined by an edge. Now the cycle C := v1v2v3v1 is a simple closed curve in the plane, and the vertex v4 must lie either in int(C) or in ext(C). Without loss of generality, we may suppose that v4 ∈ int(C). Then the edges v1v4,v2v4,v3v4 all lie entirely in int(C), too (apart from their ends v1,v2,v3) (see Figure 10.3). Consider the cycles C1 := v2v3v4v2, C2 := v3v1v4v3, and C3 := v1v2v4v1. Observe that vi ∈ ext(Ci), i = 1, 2, 3. Because viv5 ∈ E(G) and G is a plane graph, it follows from the Jordan Curve Theorem that v5 ∈ ext(Ci), i = 1, 2, 3, too. Thus v5 ∈ ext(C). But now the edge v4v5 crosses C, again by the Jordan Curve Theorem. This contradicts the planarity of the embedding G. A similar argument can be used to establish that K3,3 is nonplanar, too (Exercise 10.1.1b)
24610 Planar Graphst(C2nt(C3)nt(C)ext(C)Fig. 10.3. Proof of the nonplanarity of KsSUBDIVISIONSAny graph derived from a graph G by a sequence of edge subdivisions is calleda subdivision of G or a G-subdivision. Subdivisions of Kg and K3.3 are shown inFigure 10.4.XX(a)(b)Fig. 10.4. (a) A subdivision of Ks, (b) a subdivision of K3.3The proof of the following proposition is straightforward (Exercise 10.1.2)Proposition 10.3 A graph G is planar if and only if every subdivision of G isplanar.口BecauseKsandK3.3arenonplanar,Proposition10.3impliesthatnoplanargraph can contain a subdivision of either Ks or K3.3.A fundamental theorem dueto Kuratowski (1930) states that, conversely, every nonplanar graph necessarilycontains a copy of a subdivision of one of these two graphs. A proof of Kuratowski'sTheorem is given in Section 10.5.As mentioned in Chapter 1 and illustrated in Chapter 3, one may considerembeddings of graphs on surfaces other than the plane. We show in Section 10.6
246 10 Planar Graphs v1 v2 v3 v4 C int(C1) ext(C) int(C2) int(C3) Fig. 10.3. Proof of the nonplanarity of K5 Subdivisions Any graph derived from a graph G by a sequence of edge subdivisions is called a subdivision of G or a G-subdivision. Subdivisions of K5 and K3,3 are shown in Figure 10.4. (a) (b) Fig. 10.4. (a) A subdivision of K5, (b) a subdivision of K3,3 The proof of the following proposition is straightforward (Exercise 10.1.2). Proposition 10.3 A graph G is planar if and only if every subdivision of G is planar. Because K5 and K3,3 are nonplanar, Proposition 10.3 implies that no planar graph can contain a subdivision of either K5 or K3,3. A fundamental theorem due to Kuratowski (1930) states that, conversely, every nonplanar graph necessarily contains a copy of a subdivision of one of these two graphs. A proof of Kuratowski’s Theorem is given in Section 10.5. As mentioned in Chapter 1 and illustrated in Chapter 3, one may consider embeddings of graphs on surfaces other than the plane. We show in Section 10.6
10.1Plane and Planar Graphs247that, for every surface S, there exist graphs which are not embeddable on s.Every graphcan, however, be embedded in the 3-dimensional euclidean space R(Exercise 10.1.7).Planar graphs and graphs embeddable on the sphere are one and the same. Tosee this, we make use of a mapping known as stereographic projection. Considera sphere S resting on a plane P, and denote by z the point that is diametricallyopposite the point of contact of S and P.The mapping : SI(z] - P,defined byr(s) = p if and only if the points z, s, and p are collinear, is called a stereographicprojection from z; it is illustrated in Figure 10.5.Fig.10.5. Stereographic projectionTheorem 10.4 A graph G is embeddable on the plane if and only if it is embed-dableonthesphereProof Suppose that G has an embedding G on the sphere. Choose a point z ofthe sphere not in G. Then the image of G under stereographic projection from zis an embedding of G on the plane, The converse is proved similarly.口On many occasions, it is advantageous to consider embeddings of planar graphson the sphere; one instance is provided by the proof of Proposition 10.5 in the nextsection.Exercises+10.1.1 Show that:a) every proper subgraph of K3.3 is planar.b)K3.3isnonplanar10.1.2 Show that a graph is planar if and only if every subdivision of the graphis planar
10.1 Plane and Planar Graphs 247 that, for every surface S, there exist graphs which are not embeddable on S. Every graph can, however, be embedded in the 3-dimensional euclidean space R3 (Exercise 10.1.7). Planar graphs and graphs embeddable on the sphere are one and the same. To see this, we make use of a mapping known as stereographic projection. Consider a sphere S resting on a plane P, and denote by z the point that is diametrically opposite the point of contact of S and P. The mapping π : S \{z} → P, defined by π(s) = p if and only if the points z, s, and p are collinear, is called a stereographic projection from z; it is illustrated in Figure 10.5. z s p Fig. 10.5. Stereographic projection Theorem 10.4 A graph G is embeddable on the plane if and only if it is embeddable on the sphere. Proof Suppose that G has an embedding G on the sphere. Choose a point z of the sphere not in G. Then the image of G under stereographic projection from z is an embedding of G on the plane. The converse is proved similarly. On many occasions, it is advantageous to consider embeddings of planar graphs on the sphere; one instance is provided by the proof of Proposition 10.5 in the next section. Exercises 10.1.1 Show that: a) every proper subgraph of K3,3 is planar, b) K3,3 is nonplanar. 10.1.2 Show that a graph is planar if and only if every subdivision of the graph is planar
24810 Planar Graphs+10.1.3a) Show that the Petersen graph contains a subdivision of K3.3b) Deduce that the Petersen graph is nonplanar.+10.1.4Let G be a planar graph, and let e be a link of G. Show that G /e is planar.b)Is the converse true?+10.1.5 Let G be a simple nontrivial graph in which each vertex, except possibly one, has degree at least three. Show, by induction on n, that G contains asubdivision of K4.10.1.6 Find a planar embedding of the graph in Figure 10.6 in which each edge isstraight linesegment(Wagner (1936) proved that every simple planar graph admits such an embedding.)Fig. 10.6. Finddingof thisgraph(Exercise10.1.6)10.1.7 Ak-book isa topological subspace of R3 consisting of k unit squaralleits pages, that have one side in common, called its spine, but are pairwise disjointotherwise. Show that any graph G is embeddable in R3 by showing that it isembeddable in a k-book, for some k.10.1.8 Consider a drawing G of a (not necessarily planar) graph G in the planeTwo edges of G crossif they meet at a point other than a vertex of G.Each suchpoint is called a crossing of the two edges. The crossing number of G, denoted bycr(G), is the least number of crossings in a drawing of G in the plane. Show that:a) cr(G) = 0 if and only if G is planar.b)cr(Ks)=cr(K33)=1c) cr(Pio) = 2, where Pio is the Petersen graph,d) cr(K6) = 3
248 10 Planar Graphs 10.1.3 a) Show that the Petersen graph contains a subdivision of K3,3. b) Deduce that the Petersen graph is nonplanar. 10.1.4 a) Let G be a planar graph, and let e be a link of G. Show that G/e is planar. b) Is the converse true? 10.1.5 Let G be a simple nontrivial graph in which each vertex, except possibly one, has degree at least three. Show, by induction on n, that G contains a subdivision of K4. 10.1.6 Find a planar embedding of the graph in Figure 10.6 in which each edge is a straight line segment. (Wagner (1936) proved that every simple planar graph admits such an embedding.) Fig. 10.6. Find a straight-line planar embedding of this graph (Exercise 10.1.6) 10.1.7 A k-book is a topological subspace of R3 consisting of k unit squares, called its pages, that have one side in common, called its spine, but are pairwise disjoint otherwise. Show that any graph G is embeddable in R3 by showing that it is embeddable in a k-book, for some k. 10.1.8 Consider a drawing G of a (not necessarily planar) graph G in the plane. Two edges of G cross if they meet at a point other than a vertex of G. Each such point is called a crossing of the two edges. The crossing number of G, denoted by cr(G), is the least number of crossings in a drawing of G in the plane. Show that: a) cr(G) = 0 if and only if G is planar, b) cr(K5) = cr(K3,3) = 1, c) cr(P10) = 2, where P10 is the Petersen graph, d) cr(K6) = 3
10.2Duality24910.1.9 Show that cr(Kn)/(°) is a monotonically increasing function of n10.1.10 A graph G is crossing-minimal if cr(G /e) < cr(G) for all e E E. Showthateverynonplanaredge-transitivegraphiscrossing-minimal10.1.11 A thrackle is a graph embedded in the plane in such a way that any twoedges intersect exactly once (possibly at an end). Such an embedding is called athrackle embedding. Show that:a) every tree has a thrackle embedding.b) the 4-cycle has no thrackle embedding,c) the triangle and every cycle of length five or more has a thrackle embedding.10.1.12 Show that every simple graph can be embedded in R3 in such a way that:a) each vertex lies on the curve (t, t?, t3) : t e R],(C. THOMASSEN)b)each edge isa straight line segment10.2DualityFACESAplanegraph Gpartitions the rest oftheplaneintoanumberofarcwise-connectedopen sets. These sets are called the faces of G. Figure 10.7 shows a plane graphwith five faces, fi, f2, f3, f4, and fs. Each plane graph has exactly one unboundedface,called the outer face.In the planegraph of Figure 10.7.the outer face isfi. We denote by F(G) and f(G), respectively, the set of faces and the numberof faces of aplane graph G.Thenotion of a faceapplies alsoto embeddings ofgraphs on other surfaces.15C4Fig. 10.7. A plane graph with five faces
10.2 Duality 249 10.1.9 Show that cr(Kn)/ n 4 is a monotonically increasing function of n. 10.1.10 A graph G is crossing-minimal if cr(G \ e) < cr(G) for all e ∈ E. Show that every nonplanar edge-transitive graph is crossing-minimal. 10.1.11 A thrackle is a graph embedded in the plane in such a way that any two edges intersect exactly once (possibly at an end). Such an embedding is called a thrackle embedding. Show that: a) every tree has a thrackle embedding, b) the 4-cycle has no thrackle embedding, c) the triangle and every cycle of length five or more has a thrackle embedding. ————— ————— 10.1.12 Show that every simple graph can be embedded in R3 in such a way that: a) each vertex lies on the curve {(t,t2,t3) : t ∈ R}, b) each edge is a straight line segment. (C. Thomassen) 10.2 Duality Faces A plane graph G partitions the rest of the plane into a number of arcwise-connected open sets. These sets are called the faces of G. Figure 10.7 shows a plane graph with five faces, f1,f2,f3,f4, and f5. Each plane graph has exactly one unbounded face, called the outer face. In the plane graph of Figure 10.7, the outer face is f1. We denote by F(G) and f(G), respectively, the set of faces and the number of faces of a plane graph G. The notion of a face applies also to embeddings of graphs on other surfaces. v1 v2 v3 v5 v4 v7 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 f1 f2 f3 f4 f5 Fig. 10.7. A plane graph with five faces