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 Recog￾nition 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