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 inner266 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 face￾degree 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