27010 Planar GraphsLemma 10.33 Let G be a graph with a 2-verter cut [z,y]. Then each markedfr,yl-component ofG is isomorphicto aminor ofGProof Let H be an (r,y]-component of G, with marker edge e, and let rPy bea path in another (r,y)-component of G. Then HU P is a subgraph of G. ButHu P is isomorphic to a subdivision of G + e, so G + e is isomorphic to a minorof G.口Lemma 10.34 Let G be a graph with a 2-verter cut [z,y]. Then G is planar ifand only if each of its marked (z,y]-components is planar.Proof Suppfirstthat G is.planar.ByLemula10.33.eacmarked fr.y!componentofGisisomorphictoaminorofG,henceisplanarbyProposition1o.31Conversely, suppose that G has k marked (r,y)-components each of which isplanar. Let e denote their common marker edge. Applying Exercise 10.4.1 andinduction on k, it follows that G + e is planar, hence so is GIn view of Lemmas 10.33 and 10.34, it suffices to prove Wagner's Theorem for 3connected graphs.It remainss,therefore,to showthat every3-conmectednonplanagraph has either a Ks-minor or a K3,3-minor. We present an elegant proof of thisstatement.It is due to Thomassen (1981),and is based on his Theorem 9.10Theorem 10.35 Every 3-connected nonplanar graph has a Kuratowski minorProof Let G be a 3-connected nonplanar graph. We may assume that G is simpleBecauourorfeweotcesareplanar,wehaven>5.Weproceedgraphby induction on n. By Theorem 9.10, G contains an edge e = ry such that H :-G /e is 3-connected. If H is nonplanar, it has a Kuratowski minor, by inductionSince every minor of H is also a minor of G, we deduce that G too has a Kuratowskiminor. So we may assume that H is planar.Consider aplaneembedding H of H.Denotebyz thevertex of Hformedby contracting e. Because H is loopless and 3-connected, by Corollary 10.8 theneighboursofzlieoa cycle C.theboundary of someface f of H-z.DenotebyB, and By, respectively, the bridges of C in Gle that contain the vertices andse, first, that B and By avoid each other. In this case, Ba and By canu1be embedded in the face f of H - z in such a way that the vertices r and y belongto the same face of the resulting plane graph (H - z)uB,U By (see Figure 10.20).The edge ry can now be drawn in that face so as to obtain a planar embedding ofG itself, contradicting the hypothesis that G is nonplanalItfollows that Band B do not avoid each other.that is.they overlap.ByTheorem 10.25, they are therefore either skew or else equivalent 3-bridges. Intheforcase, G has a K3.3-minor; in the latter case, G has a Ks-minor (seeFigure 10.21).广We note that the same proof serves to show that every simple 3-connectedplanar graph admits a conver embedding, that is, a planar embedding all of whose
270 10 Planar Graphs Lemma 10.33 Let G be a graph with a 2-vertex cut {x,y}. Then each marked {x,y}-component of G is isomorphic to a minor of G. Proof Let H be an {x,y}-component of G, with marker edge e, and let xPy be a path in another {x,y}-component of G. Then H ∪ P is a subgraph of G. But H ∪ P is isomorphic to a subdivision of G + e, so G + e is isomorphic to a minor of G. Lemma 10.34 Let G be a graph with a 2-vertex cut {x,y}. Then G is planar if and only if each of its marked {x,y}-components is planar. Proof Suppose, first, that G is planar. By Lemma 10.33, each marked {x,y}- component of G is isomorphic to a minor of G, hence is planar by Proposition 10.31. Conversely, suppose that G has k marked {x,y}-components each of which is planar. Let e denote their common marker edge. Applying Exercise 10.4.1 and induction on k, it follows that G + e is planar, hence so is G. In view of Lemmas 10.33 and 10.34, it suffices to prove Wagner’s Theorem for 3- connected graphs. It remains, therefore, to show that every 3-connected nonplanar graph has either a K5-minor or a K3,3-minor. We present an elegant proof of this statement. It is due to Thomassen (1981), and is based on his Theorem 9.10. Theorem 10.35 Every 3-connected nonplanar graph has a Kuratowski minor. Proof Let G be a 3-connected nonplanar graph. We may assume that G is simple. Because all graphs on four or fewer vertices are planar, we have n ≥ 5. We proceed by induction on n. By Theorem 9.10, G contains an edge e = xy such that H := G/e is 3-connected. If H is nonplanar, it has a Kuratowski minor, by induction. Since every minor of H is also a minor of G, we deduce that G too has a Kuratowski minor. So we may assume that H is planar. Consider a plane embedding H of H. Denote by z the vertex of H formed by contracting e. Because H is loopless and 3-connected, by Corollary 10.8 the neighbours of z lie on a cycle C, the boundary of some face f of H − z. Denote by Bx and By, respectively, the bridges of C in G \ e that contain the vertices x and y. Suppose, first, that Bx and By avoid each other. In this case, Bx and By can be embedded in the face f of H −z in such a way that the vertices x and y belong to the same face of the resulting plane graph (H −z)∪Bx ∪By (see Figure 10.20). The edge xy can now be drawn in that face so as to obtain a planar embedding of G itself, contradicting the hypothesis that G is nonplanar. It follows that Bx and By do not avoid each other, that is, they overlap. By Theorem 10.25, they are therefore either skew or else equivalent 3-bridges. In the former case, G has a K3,3-minor; in the latter case, G has a K5-minor (see Figure 10.21). We note that the same proof serves to show that every simple 3-connected planar graph admits a convex embedding, that is, a planar embedding all of whose
27103Fig.10.20.Aplanar embedding of G (Br and Byavoid each other)Edb-(a)(6)Fig. 10.21. (a)A Ka.s-minor (Br and B, skew), (b)a Ks-minor (Br and B equivalent3-bridges)faces are bounded by convex polygons. All that is needed is a bit more care inplacing the bridges Br and By, and the edge e = ry, in the face f (Exercise10.5.5).There are several other interesting characterizations of planar graphs, all ofwhich can be deduced from Kuratowski's Theorem (see Exercises 10.5.7, 10.5.8,and 10.5.9).RECOGNNGPLANARGRAPHS in which it is important to decide whetherThegiven graph is planar, and ifso, tofind a planarembedding of thegraph.In thelayout of printed circuits,for example, one is interested in knowing if a particularelectrical networkisplanarIt is easy to deduce from Lemma 10.34 that a graph is planar if and onlyif each of its 3-connected components is planar.Thus the problem of decidingwhether a given graph is planar can be solved by considering each 3-connectedcomponent separately.The proof of Wagner's Theorem presented above can be
10.5 Kuratowski’s Theorem 271 x y y x Bx Bx By By Fig. 10.20. A planar embedding of G (Bx and By avoid each other) x y y x (a) (b) Fig. 10.21. (a) A K3,3-minor (Bx and By skew), (b) a K5-minor (Bx and By equivalent 3-bridges) faces are bounded by convex polygons. All that is needed is a bit more care in placing the bridges Bx and By, and the edge e = xy, in the face f (Exercise 10.5.5). There are several other interesting characterizations of planar graphs, all of which can be deduced from Kuratowski’s Theorem (see Exercises 10.5.7, 10.5.8, and 10.5.9). Recognizing Planar Graphs There are many practical situations in which it is important to decide whether a given graph is planar, and if so, to find a planar embedding of the graph. In the layout of printed circuits, for example, one is interested in knowing if a particular electrical network is planar. It is easy to deduce from Lemma 10.34 that a graph is planar if and only if each of its 3-connected components is planar. Thus the problem of deciding whether a given graph is planar can be solved by considering each 3-connected component separately. The proof of Wagner’s Theorem presented above can be
27210 Planar Graphstransformed without difficulty into a polynomial-time algorithm for determiningwhether a given 3-connected graph is planar. The idea is as follows.First, the input graph is contracted, one edge at a time, to a complete graphon four vertices (perhapswithloops and multipleedges)in such awaythat allintermediategraphs are3-connected.This contraction phase can be executed inpolynomial time by proceeding as indicated in the proof of Theorem 9.10. Theltingfour-vertex graph is then embedded in the plane. The contracted edgesesuarenow expanded oneone (in reverse order). At each stage of this exD8phase, one of two eventualities may arise: either the edge can be expanded whilepreserving planarity, and the algorithm proceeds to the next contracted edge,orelse two bridges are found which overlap, yielding a Kuratowski minor. In thesecond eventuality, the algorithm outputs one of these nonplanar minors, therebycertifying that the input graph is nonplanar. If, on the other hand, all contracted edges are expanded without encountering overlapping bridges, the algorithm outputsaplanarembeddingof GAlgorithm 10.36 PLANARITY RECOGNITION AND EMBEDDINGINpuT:a3-connectederaphGororticemnreOuTPUT: a Kuratowski minor of G or a planar embedding of G1: set i := 0 and Go := GCONTRACTIONPHASE2: whilei4dofind a link eiTiyi of Gi such that Gi/e is 3-connectedl:set Gi+1 := Gi/eireplace i by i+1end while.EXPANSION PHASE:7:find a planar embedding Gn=4 of the four-verter graph Gn-48:seti:=n-49: while i>0 dolet C, be the facial cycle of G,-zi that includes ll the neighbours of zi10:in Gi, where zi denotes the verter of Gi resulting from the contractionof the edeei-1 of Gi-let B, and B,respectively, denote the bridges ofC,containing the ver11:tices ri-1 and yi-1 in the graph obtained from Gi-1 by deleting ei-i andall other edges linking i-1 and yi-112:if B, and B' are skew then13:find a K3.3-minor K of Gi-114:returnK1公endif16:if B; and B' are equivalent 3-bridges then价拟find a Ks-minor K of Gi-1returnK19:endif20:if B, and B, avoid each other then
272 10 Planar Graphs transformed without difficulty into a polynomial-time algorithm for determining whether a given 3-connected graph is planar. The idea is as follows. First, the input graph is contracted, one edge at a time, to a complete graph on four vertices (perhaps with loops and multiple edges) in such a way that all intermediate graphs are 3-connected. This contraction phase can be executed in polynomial time by proceeding as indicated in the proof of Theorem 9.10. The resulting four-vertex graph is then embedded in the plane. The contracted edges are now expanded one by one (in reverse order). At each stage of this expansion phase, one of two eventualities may arise: either the edge can be expanded while preserving planarity, and the algorithm proceeds to the next contracted edge, or else two bridges are found which overlap, yielding a Kuratowski minor. In the second eventuality, the algorithm outputs one of these nonplanar minors, thereby certifying that the input graph is nonplanar. If, on the other hand, all contracted edges are expanded without encountering overlapping bridges, the algorithm outputs a planar embedding of G. Algorithm 10.36 planarity recognition and embedding Input: a 3-connected graph G on four or more vertices Output: a Kuratowski minor of G or a planar embedding of G 1: set i := 0 and G0 := G Contraction Phase: 2: while i<n − 4 do 3: find a link ei := xiyi of Gi such that Gi/ei is 3-connected 4: set Gi+1 := Gi/ei 5: replace i by i + 1 6: end while Expansion Phase: 7: find a planar embedding Gn−4 of the four-vertex graph Gn−4 8: set i := n − 4 9: while i > 0 do 10: let Ci be the facial cycle of Gi − zi that includes all the neighbours of zi in Gi, where zi denotes the vertex of Gi resulting from the contraction of the edge ei−1 of Gi−1 11: let Bi and B i, respectively, denote the bridges of Ci containing the vertices xi−1 and yi−1 in the graph obtained from Gi−1 by deleting ei−1 and all other edges linking xi−1 and yi−1 12: if Bi and B i are skew then 13: find a K3,3-minor K of Gi−1 14: return K 15: end if 16: if Bi and B i are equivalent 3-bridges then 17: find a K5-minor K of Gi−1 18: return K 19: end if 20: if Bi and B i avoid each other then
10.5Kuratoyci'sheo27321:ertend the planar embedding G, of G, to a planar embedding G,-1 ofGi-1ceibyi-l22:23:endif24:end while25: returm GoEach :in the contraction phase and each step in the exparsionphasecalbeexecutedipolynomialtime.Itfollowsthattheproblemofdeciding whetheragraphisplanarbelongstohereifactalinear-timeplanarityrognitonalgorithm, due to Hopcroft and Tarjan (1974). There also exist efficient planarityalgorithms based on the characterization of planarity in terms of the bridge-overlapgraph given in Exercise 10.5.7; for details, see Bondy and Murty (1976).Exercises10.5.1 Show that a simple graph has a K3-minor if and only if it contains a cycle10.5.2 Show that the (3 × 3)-grid has a K4-minor+10.5.3(a) Let F be a graph with maximum degree at nthree. Show that a graph hasn F-minor if and only if it contains an F-subdivision.b) Show that any graph which has a Kg-minor contains a Kuratowski subdivision.10.5.4 Consider the two 3-ected graphs shown in Figure 10.22. In each casecontraction oftheedge12results in agraph that is3-connected and planarObtain a planarr embedding of this resulting graph, and apply the Planarity Recognition and Embedding Algorithm (10.36) to either obtain a planar embedding ofthe given graph or else find a Kuratowski minor of the graph.10.5.5 Prove that every simple 3-connected planar graph admits aonvexplanalembedding10.5.6 Let G be a simple graph. A straight-line embedding of G is an embeddingof G in the plane in which each edge is a straight-line segment. The rectilinea?crossing number of G, denoted by cr(G) is the minimum number of crossings in astraight-line embedding of G.a) Show that:i) cr(G) ≤(G),i) if cr(G) = 1, then c(G) = 1
10.5 Kuratowski’s Theorem 273 21: extend the planar embedding Gi of Gi to a planar embedding Gi−1 of Gi−1 22: replace i by i − 1 23: end if 24: end while 25: return G0 Each step in the contraction phase and each step in the expansion phase can be executed in polynomial time. It follows that the problem of deciding whether a graph is planar belongs to P. There is, in fact, a linear-time planarity recognition algorithm, due to Hopcroft and Tarjan (1974). There also exist efficient planarity algorithms based on the characterization of planarity in terms of the bridge-overlap graph given in Exercise 10.5.7; for details, see Bondy and Murty (1976). Exercises 10.5.1 Show that a simple graph has a K3-minor if and only if it contains a cycle. 10.5.2 Show that the (3 × 3)-grid has a K4-minor. 10.5.3 a) Let F be a graph with maximum degree at most three. Show that a graph has an F-minor if and only if it contains an F-subdivision. b) Show that any graph which has a K5-minor contains a Kuratowski subdivision. 10.5.4 Consider the two 3-connected graphs shown in Figure 10.22. In each case, the contraction of the edge 12 results in a graph that is 3-connected and planar. Obtain a planar embedding of this resulting graph, and apply the Planarity Recognition and Embedding Algorithm (10.36) to either obtain a planar embedding of the given graph or else find a Kuratowski minor of the graph. ————— ————— 10.5.5 Prove that every simple 3-connected planar graph admits a convex planar embedding. 10.5.6 Let G be a simple graph. A straight-line embedding of G is an embedding of G in the plane in which each edge is a straight-line segment. The rectilinear crossing number of G, denoted by cr(G) is the minimum number of crossings in a straight-line embedding of G. a) Show that: i) cr(G) ≤ cr(G), ii) if cr(G) = 1, then cr(G) = 1
27410 Planar GraphsG1G2Fig. 10.22. Apply Algorithm 10.36 to these graphs (Exercise 10.5.4)(Bienstock and Dean (1993) have shown that cr(G) = cr(G) if G is simpleand cr(G) ≤ 3. They have also given examples of graphs G with cr(G) = 4 <cT(G).)b) Show that c(Km.n) ≤ [m/2][(m -1)/2][n/2]L(n - 1)/2],(It was conjectured by P. Turan that this bound is best possible.)10.5.7 Using Kuratowski's Theorem (10.30), show that a graph is planar if andonly if the bridge-overlap graph of each cycle is bipartite.(W.T.TUTTE)10.5.8 A basis of the cycle space of a graph is a 2-basis if each member of thebasis is a cycle of the graph, and each edge of the graph lies in at most two ofthese cyclesa) Show that:i) the cycle space of any planar graph has a 2-basis.ii)thecvclespaces ofKandKa3donothave2-basesb) A theorem due to MacLane (1937) states that a graph is planar if and only ifits cycle spacehas a 2-basis.Deduce MacLane's Theorem from Kuratowski'sTheorem (10.30)10.5.9 A graph H is called an algebraic dual of a graph G if there is a bijectionΦ : E(G) - E(H) such that a subset C of E(G) is a cycle of G if and only if (C)is a bond of Ha) Show thati) every planar graph has an algebraic dual.i) Ks and K3.3 do not have algebraic dualsb) A theorem due to Whitney (1932c) states that a graph is planar if and onlyif it has an algebraic dual. Deduce Whitney's Theorem from Kuratowski'sTheorem (10.30).10.5.10 k-SUMLet Gi and G, be two graphs whose intersection Gi nG2 is a complete graph on
274 10 Planar Graphs 1 1 2 2 3 3 5 4 5 4 6 6 7 7 8 8 G1 G2 Fig. 10.22. Apply Algorithm 10.36 to these graphs (Exercise 10.5.4) (Bienstock and Dean (1993) have shown that cr(G) = cr(G) if G is simple and cr(G) ≤ 3. They have also given examples of graphs G with cr(G)=4 < cr(G).) b) Show that cr(Km,n) ≤ m/2(m − 1)/2n/2(n − 1)/2. (It was conjectured by P. Tur´an that this bound is best possible.) 10.5.7 Using Kuratowski’s Theorem (10.30), show that a graph is planar if and only if the bridge-overlap graph of each cycle is bipartite. (W.T. Tutte) 10.5.8 A basis of the cycle space of a graph is a 2-basis if each member of the basis is a cycle of the graph, and each edge of the graph lies in at most two of these cycles. a) Show that: i) the cycle space of any planar graph has a 2-basis, ii) the cycle spaces of K5 and K3,3 do not have 2-bases. b) A theorem due to MacLane (1937) states that a graph is planar if and only if its cycle space has a 2-basis. Deduce MacLane’s Theorem from Kuratowski’s Theorem (10.30). 10.5.9 A graph H is called an algebraic dual of a graph G if there is a bijection φ : E(G) → E(H) such that a subset C of E(G) is a cycle of G if and only if φ(C) is a bond of H. a) Show that: i) every planar graph has an algebraic dual, ii) K5 and K3,3 do not have algebraic duals. b) A theorem due to Whitney (1932c) states that a graph is planar if and only if it has an algebraic dual. Deduce Whitney’s Theorem from Kuratowski’s Theorem (10.30). 10.5.10 k-Sum Let G1 and G2 be two graphs whose intersection G1 ∩ G2 is a complete graph on