In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by, and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.
Definitions
A peripheral cycle in a graph can be defined formally in one of several equivalent ways:
is peripheral if it is a simple cycle in a connected graph with the property that, for every two edges and in, there exists a path in that starts with, ends with, and has no interior vertices belonging to.
is peripheral if it is an induced cycle with the property that the subgraph formed by deleting the edges and vertices of is connected.
If is any subgraph of, a bridge of is a minimal subgraph of that is edge-disjoint from and that has the property that all of its points of attachments belong to. A simple cycle is peripheral if it has exactly one bridge.
The equivalence of these definitions is not hard to see: a connected subgraph of , 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.
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 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 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 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, 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.
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 such that deleting the circuit leaves a smaller matroid that is connected. These are analogous to peripheral cycles, but not the same even in graphic matroids. For example, in the complete bipartite graph, every cycle is peripheral but the graphic matroid formed by this bridge is not connected, so no circuit of the graphic matroid of is non-separating.
