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 then272 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 out￾puts 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 ver￾tices 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