10.4 Bridges265bridge contained in Int(C) is called an inner bridge, a bridge contained in Ext(C)an outer bridge. In Figure 10.16, Bi and B, are inner bridges, and Bg and By areouter bridges.Theorem 10.26 Inner (outer) bridges avoid one another.Proof Let B and B' be inner bridges of a cycle C in a plane graph G. Supposethattheyoverlap.ByTheorem10.25,theyareeitherskeworequivalent3-bridges.In both cases, we obtain contradictionsCase I: B and B' are skew. By definition, there exist distinct vertices u,u in B andu', u' in B', appearing in the cyclic order u, u,v, u' on C. Let uPu be a path in Band u'P'u'a path in B',both intermally disjoint from C.Consider the subgraphH := CU PU P' of G (see Figure 10.17a). Because G is plane, so is H. Let Kbe the plane graph obtained from H by adding a vertex in ext(C) and joiningit to u,u',v,u' (see Figure 10.17b). Then K is a subdivision of Ks. But this isimpossible.Ksbeingnonplanar(b)(a)Fig.10.17.Proof of Theorem 10.26, Case 1: (a) the subgraph H, (b) the subdivision KofKsCase 2: B and B' are equivalent 3-bridges, Denote by S := [ui, u2, u3] theirmon set of vertices of attachment. By Exercise 9.2.3, there exists a (u, S)-fanFin B, for some internal vertex ofB; likewise, thereexists a (u,)-fan F'inB', for some internal vertex u' of B'. Consider the subgraph H := F U F" of G.Because G is plane, so is H.Let K be the plane graph obtained from H byaddinga vertexin ext(C)and joining it to thethreevertices of S.Then K is a subdivisionof K3.3. But this is impossible, because K3.3 is nonplanar (see Figure 10.18)We conclude that inner bridges avoid one another. Similarly, outer bridgavoid one anotherIt is convenient to visualize the above theorem in terms of the bridge-overlapgraph. Let G be a graph and let C be a cycle of G. The bridge-overlap graph of Cis the graph whose vertex set is the set of all bridges of C in G, two bridges being
10.4 Bridges 265 bridge contained in Int(C) is called an inner bridge, a bridge contained in Ext(C) an outer bridge. In Figure 10.16, B1 and B2 are inner bridges, and B3 and B4 are outer bridges. Theorem 10.26 Inner (outer) bridges avoid one another. Proof Let B and B be inner bridges of a cycle C in a plane graph G. Suppose that they overlap. By Theorem 10.25, they are either skew or equivalent 3-bridges. In both cases, we obtain contradictions. Case 1: B and B are skew. By definition, there exist distinct vertices u,v in B and u ,v in B , appearing in the cyclic order u,u ,v,v on C. Let uPv be a path in B and u P v a path in B , both internally disjoint from C. Consider the subgraph H := C ∪ P ∪ P of G (see Figure 10.17a). Because G is plane, so is H. Let K be the plane graph obtained from H by adding a vertex in ext(C) and joining it to u,u ,v,v (see Figure 10.17b). Then K is a subdivision of K5. But this is impossible, K5 being nonplanar. P P u v u v (a) (b) Fig. 10.17. Proof of Theorem 10.26, Case 1: (a) the subgraph H, (b) the subdivision K of K5 Case 2: B and B are equivalent 3-bridges. Denote by S := {v1,v2,v3} their common set of vertices of attachment. By Exercise 9.2.3, there exists a (v,S)-fan F in B, for some internal vertex v of B; likewise, there exists a (v ,S)-fan F in B , for some internal vertex v of B . Consider the subgraph H := F ∪ F of G. Because G is plane, so is H. Let K be the plane graph obtained from H by adding a vertex in ext(C) and joining it to the three vertices of S. Then K is a subdivision of K3,3. But this is impossible, because K3,3 is nonplanar (see Figure 10.18). We conclude that inner bridges avoid one another. Similarly, outer bridges avoid one another. It is convenient to visualize the above theorem in terms of the bridge-overlap graph. Let G be a graph and let C be a cycle of G. The bridge-overlap graph of C is the graph whose vertex set is the set of all bridges of C in G, two bridges being
26610 Planar Graphs(a)(6)Fig. 10.18. Proof of Theorem 10.26, Case 2: (a) the subgraph H, (b) the subdivision KofK3,3adjacent ifthey overlap.Theorem 10.26 simply states that thebridge-overlapgraphof any cvcleof a plane praph is bipartite.Thus.anecessary condition for a eraphto be planar is that the bridge-overlap graph of each of its cycles be bipartite. Thiscondition also suffices to guarantee planarity (Exercise 10.5.7).UNIQUE PLANE EMBEDDINGSJust as there is no unique way of representing graphs by diagrams, there is nographs in the plane. Apart from the positionsuniqueway ofembeddingplanarof points representing vertices and the shapes of lines representing the edges,twodifferent planar embeddings of the same planar graph may difer in the incidencerelationships between their edge and face sets; they may even have different facedegree sequences, as in Figure 10.11. We say that two planar embeddings of aplanar graph G are equivalentif theirface boundaries (regarded as sets of edges)are identical. A planar graph for which any two planar embeddings are equivalent issaid have an unique embedding in the plane. Using the theory of bridges developedabove,we showthatevery simple3-connected planar graphis uniquelyembeddablenote that the graph of Figure 10.11 is not 3-connected. The notionintheplaneof anonseparating cycle plays a crucial role in thisproofntrivial bridgeA cvcle is nonseparating if it has no chords and at most Thusmooplessgraph Gwhich isnot itsefacyleacyceCisnoneparatiif and only if it is an induced subgraph of G and G -V(C) is connected. Inthe case of simple 3-connected plane graphs, Tutte (1963) proved that facial andnonseparating cvcles are one and the same.The0rem 10.27 A cycle in a simple 3-connected plane graph is a facial cycle ifand only if it is nonseparating.Proof Let G be a simple 3-connected plane graph and let C be a cycle of GSuppose, first, that C is not a facial cycle of G. Then C has at least one inner
266 10 Planar Graphs v1 v2 v3 v v (a) (b) Fig. 10.18. Proof of Theorem 10.26, Case 2: (a) the subgraph H, (b) the subdivision K of K3,3 adjacent if they overlap. Theorem 10.26 simply states that the bridge-overlap graph of any cycle of a plane graph is bipartite. Thus, a necessary condition for a graph to be planar is that the bridge-overlap graph of each of its cycles be bipartite. This condition also suffices to guarantee planarity (Exercise 10.5.7). Unique Plane Embeddings Just as there is no unique way of representing graphs by diagrams, there is no unique way of embedding planar graphs in the plane. Apart from the positions of points representing vertices and the shapes of lines representing the edges, two different planar embeddings of the same planar graph may differ in the incidence relationships between their edge and face sets; they may even have different facedegree sequences, as in Figure 10.11. We say that two planar embeddings of a planar graph G are equivalent if their face boundaries (regarded as sets of edges) are identical. A planar graph for which any two planar embeddings are equivalent is said have an unique embedding in the plane. Using the theory of bridges developed above, we show that every simple 3-connected planar graph is uniquely embeddable in the plane; note that the graph of Figure 10.11 is not 3-connected. The notion of a nonseparating cycle plays a crucial role in this proof. A cycle is nonseparating if it has no chords and at most one nontrivial bridge. Thus, in a loopless graph G which is not itself a cycle, a cycle C is nonseparating if and only if it is an induced subgraph of G and G − V (C) is connected. In the case of simple 3-connected plane graphs, Tutte (1963) proved that facial and nonseparating cycles are one and the same. Theorem 10.27 A cycle in a simple 3-connected plane graph is a facial cycle if and only if it is nonseparating. Proof Let G be a simple 3-connected plane graph and let C be a cycle of G. Suppose, first, that C is not a facial cycle of G. Then C has at least one inner
10.4 Bridges267bridge and at least one outer bridge. Because G is simple and connected, thesebridgeis either they are both nontrivial or at least one of themos.is a chord. It follows that C is not a nonseparating cycle.Now suppose that C is a facial cycle of G. By Proposition 10.5, we may assurthat C bounds the outer face of G, so all its bridges are inner bridges. By Theorem 10.26, these bridges avoid one another. If C had a chord ry, the set (r,ywonld be a vertex cut separating the internal vertices of the two ry-segments of C.Likewise, if C had two nontrivial bridges, the vertices of attachment of one of thesebridges would all lie on a single y-segment of the other bridge, and (z,y) wouldbe a vertex cut of G separating the internal vertices of the two bridges. In eithercase, the 3-connectedness of G would be contradicted. Thus C is nonseparating.口A direct conseence of Theorem 10.27 is the following fundamental theorem,duetoWhitney(1933)Theorem 10.28 Every simple 3-connected planar graph has a unique planar embedding.ProofLet Gbea simple3-connected planar graph.By Theorem 10.27,thefacialcycles in any planar embedding of G are precisely its nonseparating cycles. Becausethelater aredefined solely iterms oftheabstract structureofthegraph,theyare the same for every planar embedding of G.口The following corollary is immediateCorollary 10.29 Every simple 3-connected planar graph has a unique dual graph口Exercises+10.4.1 Let Gh and G2 be planar graphs whoserphic to K2ShowthatGUG2isplanar10.4.2 Let H be a subgraph of a graph G. Consider the binary relation ~ onE(G) /E(H), where ei ~ e2 if there exists a walk W in G such that:D the first and the last edges of W are e1 and e2, respectively,Wis internallydisjoint from H (that is,nointernal vertexofWisavertexofH).Show that:a) the relation ~ is an equivalence relation on E(G) / E(H)b) the subgraphs of G/E(H) induced by the equivalence classes under this equivalence relation are the bridges of H in G
10.4 Bridges 267 bridge and at least one outer bridge. Because G is simple and connected, these bridges are not loops. Thus either they are both nontrivial or at least one of them is a chord. It follows that C is not a nonseparating cycle. Now suppose that C is a facial cycle of G. By Proposition 10.5, we may assume that C bounds the outer face of G, so all its bridges are inner bridges. By Theorem 10.26, these bridges avoid one another. If C had a chord xy, the set {x,y} would be a vertex cut separating the internal vertices of the two xy-segments of C. Likewise, if C had two nontrivial bridges, the vertices of attachment of one of these bridges would all lie on a single xy-segment of the other bridge, and {x,y} would be a vertex cut of G separating the internal vertices of the two bridges. In either case, the 3-connectedness of G would be contradicted. Thus C is nonseparating. A direct consequence of Theorem 10.27 is the following fundamental theorem, due to Whitney (1933). Theorem 10.28 Every simple 3-connected planar graph has a unique planar embedding. Proof Let G be a simple 3-connected planar graph. By Theorem 10.27, the facial cycles in any planar embedding of G are precisely its nonseparating cycles. Because the latter are defined solely in terms of the abstract structure of the graph, they are the same for every planar embedding of G. The following corollary is immediate. Corollary 10.29 Every simple 3-connected planar graph has a unique dual graph. Exercises 10.4.1 Let G1 and G2 be planar graphs whose intersection is isomorphic to K2. Show that G1 ∪ G2 is planar. 10.4.2 Let H be a subgraph of a graph G. Consider the binary relation ∼ on E(G) \ E(H), where e1 ∼ e2 if there exists a walk W in G such that: the first and the last edges of W are e1 and e2, respectively, W is internally disjoint from H (that is, no internal vertex of W is a vertex of H). Show that: a) the relation ∼ is an equivalence relation on E(G) \ E(H), b) the subgraphs of G\E(H) induced by the equivalence classes under this equivalence relation are the bridges of H in G. ————— —————
26810 Planar Graphs10.4.3 A 3-polytope is the convex hull of a set of points in R3 which do not lieon a common plane. Show that the polyhedral graph of such a polytope is simple.planar,and 3-connected.(Steinitz (1922) proved that, conversely, every simple 3-conncted planar graph isthe polyhedral graph of some 3-polytope.)10.4.4 Show that any 3-connected cubic plane graph on n vertices, where n >may be obtained from one on n -- 2 vertices by subdividing two edges in theboundary of a face and joining the resulting new vertices by an edge subdividingthe face.10.4.5 Arooting ofa plane graph Gis atriple (,,f), where is a vertex, calederte, e is an edge of G incident with v, called the root edge, and f is ao0face incident with e, called the root face.a) Show that the only automorphism of a simple 3-connected plane graph whichixes a given rooting is the identity automorphismb) Let G be a simple 3-connected planar graph. Deduce from (a) that:)aut(G)divides4m,i) aut(G) = 4m if and only if G is one of the five platonic graphs(F.HARARY AND W.T. TUTTE; L. WEINBERG)10.5 Kuratowski's TheoremPlanarity being such a fundamental property, the problem of deciding whether agiven graph is planar is clearly of great inortance. A major step towards this goalis provided by thefollowing characterization of planar graphs, due to Kuratowski(1930).Theorem10.30KURATOWSKI'STHEOREMA graph is planar if and only if it contains no subdivision of either K, or K3.3A subdivision of Ks or K3.3 is consequently called a Kuratouski subdivisionWe first present a proof of Kuratowski's Theorem due to Thomassen (1981)and then explain how it gives rise to a polynomial-time decision algorithm forplanarity.Beforeprovingthetheorem,wereformulateitintermsofminorsMINORSA minor of a graph G is any graph obtainable from G by means of a sequence ofvertex and edge deletions and edge contractions.Alternatively,consider apartition(Vo, Vi,..., Ve) of V such that G[V] is connected, 1 < i < k, and let H be thegraph obtained from G by deleting Vo and shrinking each induced subgraph G[V],<i≤ k, to a single vertex. Then aly spanning subgraph F of H is a nG.For instance, K,is aminor of the Petersen graph because it can be obtainedby contracting the five 'spoke' edges of the latter graph (see Figure 10.19)
268 10 Planar Graphs 10.4.3 A 3-polytope is the convex hull of a set of points in R3 which do not lie on a common plane. Show that the polyhedral graph of such a polytope is simple, planar, and 3-connected. (Steinitz (1922) proved that, conversely, every simple 3-connected planar graph is the polyhedral graph of some 3-polytope.) 10.4.4 Show that any 3-connected cubic plane graph on n vertices, where n ≥ 6, may be obtained from one on n − 2 vertices by subdividing two edges in the boundary of a face and joining the resulting new vertices by an edge subdividing the face. 10.4.5 A rooting of a plane graph G is a triple (v,e,f), where v is a vertex, called the root vertex, e is an edge of G incident with v, called the root edge, and f is a face incident with e, called the root face. a) Show that the only automorphism of a simple 3-connected plane graph which fixes a given rooting is the identity automorphism. b) Let G be a simple 3-connected planar graph. Deduce from (a) that: i) aut(G) divides 4m, ii) aut(G)=4m if and only if G is one of the five platonic graphs. (F. Harary and W.T. Tutte; L. Weinberg) 10.5 Kuratowski’s Theorem Planarity being such a fundamental property, the problem of deciding whether a given graph is planar is clearly of great importance. A major step towards this goal is provided by the following characterization of planar graphs, due to Kuratowski (1930). Theorem 10.30 Kuratowski’s Theorem A graph is planar if and only if it contains no subdivision of either K5 or K3,3. A subdivision of K5 or K3,3 is consequently called a Kuratowski subdivision. We first present a proof of Kuratowski’s Theorem due to Thomassen (1981), and then explain how it gives rise to a polynomial-time decision algorithm for planarity. Before proving the theorem, we reformulate it in terms of minors. Minors A minor of a graph G is any graph obtainable from G by means of a sequence of vertex and edge deletions and edge contractions. Alternatively, consider a partition (V0,V1,...,Vk) of V such that G[Vi] is connected, 1 ≤ i ≤ k, and let H be the graph obtained from G by deleting V0 and shrinking each induced subgraph G[Vi], 1 ≤ i ≤ k, to a single vertex. Then any spanning subgraph F of H is a minor of G. For instance, K5 is a minor of the Petersen graph because it can be obtained by contracting the five ‘spoke’ edges of the latter graph (see Figure 10.19)
26910.5Fig. 10.19. Contracting the Petersen graph to KsIf F is a minoiorofG.wewriteF<G.ByanF-minorofG.whereFisalarbitrary graph, we mean anorofG whichis isomorphic to F.It is importanttopoint out that any graph whichcontains an F-subdivision alsohas an F-minor:to obtain F as a minor, one simply deletes the vertices and edges not im thesubdivision, and then contracts each subdivided edge to a single edge.For examplebecause the Petersen graph contains a K3.3-subdivision (Exercise 10.1.3), it alsohas a K3.3-minor, Conversely, provided that F is a graph of maximum degreethree or less, any graph which has an F-minor also contains an F-subdivision(Exercise 10.5.3a)WAGNER'S THEOREMAs observed in Section i0.2, the deletion or contraction of an edge in a planargraph results again in a planar graph. Thus we haves口Proposition 10.31 Minors of planar graphs are planarA minor which is isomorphic to K, or K3.3 is called a Kuratouski minor. Because Ks and K3,3 are nonplanar, Proposition 10.31 implies that any graph whichhas a Kuratowski minor is nonplanar. Wagner (1937) proved that the converse istrueWAGNER'STHEOREMTheorem 10.32A graph is planar if and only if it has no Kuratowski minoWererked above thataph which coF-subdivisionalsnhtF-minor.Thus Kuratowski's Theorem implies Wagner's Theorem.On the otherhand, because K3.3 has maximum degree three, any graph which has a K-contains a K3,3-subdivision (Exercise 10.5.3a).Furthermore, any graph which hasa Kg-minor necessarily contains a Kuratowski subdivision (Exercise 10.5.3b). ThusWagner's Theorem implies Kuratowski's Theorem, and the two are therefore equiv-alentIt turns out to be slightly more convenient to prove Wagner's variant of Kura-towski's Theorem. Before doing so, we need to establish two simple lemmas
10.5 Kuratowski’s Theorem 269 Fig. 10.19. Contracting the Petersen graph to K5 If F is a minor of G, we write F G. By an F-minor of G, where F is an arbitrary graph, we mean a minor of G which is isomorphic to F. It is important to point out that any graph which contains an F-subdivision also has an F-minor: to obtain F as a minor, one simply deletes the vertices and edges not in the subdivision, and then contracts each subdivided edge to a single edge. For example, because the Petersen graph contains a K3,3-subdivision (Exercise 10.1.3), it also has a K3,3-minor. Conversely, provided that F is a graph of maximum degree three or less, any graph which has an F-minor also contains an F-subdivision (Exercise 10.5.3a). Wagner’s Theorem As observed in Section 10.2, the deletion or contraction of an edge in a planar graph results again in a planar graph. Thus we have: Proposition 10.31 Minors of planar graphs are planar. A minor which is isomorphic to K5 or K3,3 is called a Kuratowski minor. Because K5 and K3,3 are nonplanar, Proposition 10.31 implies that any graph which has a Kuratowski minor is nonplanar. Wagner (1937) proved that the converse is true. Theorem 10.32 Wagner’s Theorem A graph is planar if and only if it has no Kuratowski minor. We remarked above that a graph which contains an F-subdivision also has an F-minor. Thus Kuratowski’s Theorem implies Wagner’s Theorem. On the other hand, because K3,3 has maximum degree three, any graph which has a K3,3-minor contains a K3,3-subdivision (Exercise 10.5.3a). Furthermore, any graph which has a K5-minor necessarily contains a Kuratowski subdivision (Exercise 10.5.3b). Thus Wagner’s Theorem implies Kuratowski’s Theorem, and the two are therefore equivalent. It turns out to be slightly more convenient to prove Wagner’s variant of Kuratowski’s Theorem. Before doing so, we need to establish two simple lemmas