Peripheral Cycle - Properties

Properties

Peripheral cycles appear in the theory of polyhedral graphs, that is, 3-vertex-connected planar graphs. For every planar graph, and every planar embedding of, the faces of the embedding that are induced cycles must be peripheral cycles. In a polyhedral graph, all faces are peripheral cycles, and every peripheral cycle is a face. It follows from this fact that (up to combinatorial equivalence, the choice of the outer face, and the orientation of the plane) every polyhedral graph has a unique planar embedding.

In planar graphs, the cycle space is generated by the faces, but in non-planar graphs peripheral cycles play a similar role: for every 3-vertex-connected finite graph, the cycle space is generated by the peripheral cycles. The result can also be extended to locally-finite but infinite graphs. In particular, it follows that 3-connected graphs are guaranteed to contain peripheral cycles. There exist 2-connected graphs that do not contain peripheral cycles (an example is the complete bipartite graph, for which every cycle has two bridges) but if a 2-connected graph has minimum degree three then it contains at least one peripheral cycle.

In some algorithms for testing planarity of graphs, it is useful to find a cycle that is not peripheral, in order to partition the problem into smaller subproblems. In a biconnected graph of circuit rank less than three (such as a cycle graph or theta graph) every cycle is peripheral, but every biconnected graph with circuit rank three or more has a non-peripheral cycle, which may be found in linear time.

Generalizing chordal graphs, Weaver & Seymour (1984) define a strangulated graph to be a graph in which every peripheral cycle is a triangle. They characterize these graphs as being the clique-sums of chordal graphs and maximal planar graphs.