Peripheral cycle

Peripheral cycles (or, as they were initially called, peripheral polygons, because Tutte called cycles "polygons") were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.

), 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

[8] 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.

[10] The result can also be extended to locally-finite but infinite graphs.

[12] Peripheral cycles in 3-connected graphs can be computed in linear time and have been used for designing planarity tests.

[13] 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.

[18] 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).

, 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

In this graph, the red triangle formed by vertices 1, 2, and 5 is a peripheral cycle: the four remaining edges form a single bridge. However, pentagon 1–2–3–4–5 is not peripheral, as the two remaining edges form two separate bridges.