Peripheral cycle

Definitions

A peripheral cycle C in a graph G can be defined formally in one of several equivalent ways:

The equivalence of these definitions is not hard to see: a connected subgraph of G ∖ C (together with the edges linking it to C ), or a chord of a cycle that causes it to fail to be induced, must in either case be a bridge, and must also be an equivalence class of the binary relation on edges in which two edges are related if they are the ends of a path with no interior vertices in C .

Properties

Peripheral cycles appear in the theory of polyhedral graphs, that is, 3-vertex-connected planar graphs. For every planar graph G , and every planar embedding of G , 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 K 2 , 4 , 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.

Peripheral cycles in 3-connected graphs can be computed in linear time and have been used for designing planarity tests. They were also extended to the more general notion of non-separating ear decompositions. 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, Seymour & Weaver (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.

Related concepts

Peripheral cycles have also been called non-separating cycles, but this term is ambiguous, as it has also been used for two related but distinct concepts: simple cycles the removal of which would disconnect the remaining graph, and cycles of a topologically embedded graph such that cutting along the cycle would not disconnect the surface on which the graph is embedded.

In matroids, a non-separating circuit is a circuit of the matroid (that is, a minimal dependent set) such that deleting the circuit leaves a smaller matroid that is connected (that is, that cannot be written as a direct sum of matroids). These are analogous to peripheral cycles, but not the same even in graphic matroids (the matroids whose circuits are the simple cycles of a graph). For example, in the complete bipartite graph K 2 , 3 , every cycle is peripheral (it has only one bridge, a two-edge path) but the graphic matroid formed by this bridge is not connected, so no circuit of the graphic matroid of K 2 , 3 is non-separating.