26410 Planar GraphsBRIDGES OF CYCLEWe bridges of cycles, and all bridgesbe bridges of a given cycle C. Thus, to avoid repetition, we abbreviate bridge ofC' to ‘bridge' in the coming discussionThe vertices of attachment of a k-bridge B with k ≥ 2 effect a partition ofC into k edge-disjoint paths, called the segments of B. Two bridges avoid eachotherifall thevertices of attachment of onebridge liein asinglesegment oftheother bridge:otherwise,they overlap.InFigure10.15,B2and Bavoid each otherwhereas B and B2 overlap, as do B3 and Ba. Two bridges B and B' are skew ifthere are distinct vertices of attachment u,u of B,and u.u'of B',which occur inthecyclic order u,u,,u'on C.In Figure0.15, B and B are skew, whereas andBaarenotTheorem 10.25 Overlapping bridges are either skew or else equivalent 3-bridges.Proof Suppose that bridges B and B' overlap. Clearly, each must have at leasttwo vertices of attachment. If either B or B' is a 2-bridge, it is easily verified thatthey must be skew. We may therefore assume that both B and B' have at leastthree vertices of attachmentralent bridges, then B' has a vertex u' of attachmentIf B and B' are not equiyiment u and u of B. Because B andoetweentwoconsecutiveverticesof attaB'overlap,somevertexofattachment'ofB'doesnot lieinthesegmentofBconnecting u and v. It follows that B and B' are skew.If B and B' are equivalent k-bridges, then k ≥ 3. If k ≥ 4, B and B' are skewif k =- 3, they are equivalent 3-bridges口BB:Fig. 10.16. Bridges of a cycle in a plane graphWe now consider bridges of cycles in planegraphs. Suppose that Gis aplanegraph and that C is a cycle in G. Because C is a simple closed curve in the planeeach bridge of C in G is contained in one of the two regions Int(C) or Ext(C). A264 10 Planar Graphs Bridges of Cycles We are concerned here with bridges of cycles, and all bridges are understood to be bridges of a given cycle C. Thus, to avoid repetition, we abbreviate ‘bridge of C’ to ‘bridge’ in the coming discussion. The vertices of attachment of a k-bridge B with k ≥ 2 effect a partition of C into k edge-disjoint paths, called the segments of B. Two bridges avoid each other if all the vertices of attachment of one bridge lie in a single segment of the other bridge; otherwise, they overlap. In Figure 10.15, B2 and B3 avoid each other, whereas B1 and B2 overlap, as do B3 and B4. Two bridges B and B are skew if there are distinct vertices of attachment u,v of B, and u ,v of B , which occur in the cyclic order u,u ,v,v on C. In Figure 10.15, B3 and B4 are skew, whereas B1 and B2 are not. Theorem 10.25 Overlapping bridges are either skew or else equivalent 3-bridges. Proof Suppose that bridges B and B overlap. Clearly, each must have at least two vertices of attachment. If either B or B is a 2-bridge, it is easily verified that they must be skew. We may therefore assume that both B and B have at least three vertices of attachment. If B and B are not equivalent bridges, then B has a vertex u of attachment between two consecutive vertices of attachment u and v of B. Because B and B overlap, some vertex of attachment v of B does not lie in the segment of B connecting u and v. It follows that B and B are skew. If B and B are equivalent k-bridges, then k ≥ 3. If k ≥ 4, B and B are skew; if k = 3, they are equivalent 3-bridges.
B1 B2 B3 B4 Fig. 10.16. Bridges of a cycle in a plane graph We now consider bridges of cycles in plane graphs. Suppose that G is a plane graph and that C is a cycle in G. Because C is a simple closed curve in the plane, each bridge of C in G is contained in one of the two regions Int(C) or Ext(C). A