Peripheral cycle

<h2 id="definitions">Definitions</h2>
A peripheral cycle 
 
 
 
 C
 
 
 {\displaystyle C}
 
 in a graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
 can be defined formally in one of several equivalent ways:

<ul><li>
 
 
 
 C
 
 
 {\displaystyle C}
 
 is peripheral if it is a <a href="/facts/Simple_cycle/Is44edrv">simple cycle</a> in a <a href="/facts/Connected_graph/FSNjsYhz">connected graph</a> with the property that, for every two edges 
 
 
 
 
 e
 
 1
 
 
 
 
 {\displaystyle e_{1}}
 
 and 
 
 
 
 
 e
 
 2
 
 
 
 
 {\displaystyle e_{2}}
 
 in 
 
 
 
 G
 ∖
 C
 
 
 {\displaystyle G\setminus C}
 
, there exists a path in 
 
 
 
 G
 
 
 {\displaystyle G}
 
 that starts with 
 
 
 
 
 e
 
 1
 
 
 
 
 {\displaystyle e_{1}}
 
, ends with 
 
 
 
 
 e
 
 2
 
 
 
 
 {\displaystyle e_{2}}
 
, and has no interior vertices belonging to 
 
 
 
 C
 
 
 {\displaystyle C}
 
.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li>If 
 
 
 
 C
 
 
 {\displaystyle C}
 
 is any subgraph of 
 
 
 
 G
 
 
 {\displaystyle G}
 
, a bridge<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> of 
 
 
 
 C
 
 
 {\displaystyle C}
 
 is a minimal subgraph 
 
 
 
 B
 
 
 {\displaystyle B}
 
 of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 that is edge-disjoint from 
 
 
 
 C
 
 
 {\displaystyle C}
 
 and that has the property that all of its points of attachments (vertices adjacent to edges in both 
 
 
 
 B
 
 
 {\displaystyle B}
 
 and 
 
 
 
 G
 ∖
 B
 
 
 {\displaystyle G\setminus B}
 
) belong to 
 
 
 
 C
 
 
 {\displaystyle C}
 
.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> A simple cycle 
 
 
 
 C
 
 
 {\displaystyle C}
 
 is peripheral if it has exactly one bridge.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>In a connected graph that is not a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">theta graph</a>, peripheral cycles cannot have chords, because any chord would be a bridge, separated from the rest of the graph. In this case, 
 
 
 
 C
 
 
 {\displaystyle C}
 
 is peripheral if it is an <a href="/facts/Induced_cycle/zfcIx9Sw">induced cycle</a> with the property that the subgraph 
 
 
 
 G
 ∖
 C
 
 
 {\displaystyle G\setminus C}
 
 formed by deleting the edges and vertices of 
 
 
 
 C
 
 
 {\displaystyle C}
 
 is connected.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li></ul>
The equivalence of these definitions is not hard to see: a connected subgraph of 
 
 
 
 G
 ∖
 C
 
 
 {\displaystyle G\setminus C}
 
 (together with the edges linking it to 
 
 
 
 C
 
 
 {\displaystyle 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 <a href="/facts/Equivalence_class/1d2sh0TB">equivalence class</a> of the <a href="/facts/Binary_relation/r9BwGgaK">binary relation</a> on edges in which two edges are related if they are the ends of a path with no interior vertices in 
 
 
 
 C
 
 
 {\displaystyle C}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="properties">Properties</h2>
Peripheral cycles appear in the theory of <a href="/facts/Polyhedral_graph/IKPCDH6r">polyhedral graphs</a>, that is, <a href="/facts/K-vertex-connected_graph/EST9uf8W">3-vertex-connected</a> <a href="/facts/Planar_graph/plREagr9">planar graphs</a>. For every planar graph 
 
 
 
 G
 
 
 {\displaystyle G}
 
, and every planar embedding of 
 
 
 
 G
 
 
 {\displaystyle 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> 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.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
In planar graphs, the <a href="/facts/Cycle_space/NeWx2guT">cycle space</a> 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.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> The result can also be extended to locally-finite but infinite graphs.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> 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 <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> 
 
 
 
 
 K
 
 2
 ,
 4
 
 
 
 
 {\displaystyle 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.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
Peripheral cycles in 3-connected graphs can be computed in linear time and have been used for designing planarity tests.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
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 <a href="/facts/Circuit_rank/RqbfVDR6">circuit rank</a> less than three (such as a <a href="/facts/Cycle_graph/bYhnPDHc">cycle graph</a> or <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">theta graph</a>) 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.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
Generalizing <a href="/facts/Chordal_graph/7hNerUdA">chordal graphs</a>, Seymour & Weaver (1984) define a <a href="/facts/Strangulated_graph/6v1R7gTf">strangulated graph</a> to be a graph in which every peripheral cycle is a triangle. They characterize these graphs as being the <a href="/facts/Clique-sum/AkdxYjMR">clique-sums</a> of chordal graphs and <a href="/facts/Maximal_planar_graph/plREagr9">maximal planar graphs</a>.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

<h2 id="related-concepts">Related concepts</h2>
Peripheral cycles have also been called non-separating cycles,<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> 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,<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> and cycles of a <a href="/facts/Graph_embedding/IyBA3ttM">topologically embedded graph</a> such that cutting along the cycle would not disconnect the surface on which the graph is embedded.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
In <a href="/facts/Matroid/5bLcGlRF">matroids</a>, a non-separating circuit is a circuit of the matroid (that is, a minimal dependent set) such that <a href="/facts/Matroid_minor/nrEV2Sn2">deleting</a> the circuit leaves a smaller matroid that is connected (that is, that cannot be written as a direct sum of matroids).<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> These are analogous to peripheral cycles, but not the same even in <a href="/facts/Graphic_matroid/UkEwWWhl">graphic matroids</a> (the matroids whose circuits are the simple cycles of a graph). For example, in the <a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> 
 
 
 
 
 K
 
 2
 ,
 3
 
 
 
 
 {\displaystyle 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
 
 
 
 
 {\displaystyle K_{2,3}}
 
 is non-separating.

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387. <a href="/wiki/W._T._Tutte" target="_blank">/wiki/W._T._Tutte</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 74–75, ISBN 978-0-13-301615-4. <a href="978-0-13-301615-4" target="_blank">978-0-13-301615-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Not to be confused with bridge (graph theory), a different concept. <a href="/wiki/Bridge_(graph_theory)" target="_blank">/wiki/Bridge_(graph_theory)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Tutte, W. T. (1960), "Convex representations of graphs", Proceedings of the London Mathematical Society, Third Series, 10: 304–320, doi:10.1112/plms/s3-10.1.304, MR 0114774. <a href="/wiki/W._T._Tutte" target="_blank">/wiki/W._T._Tutte</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">This is the definition of peripheral cycles originally used by Tutte (1963). Seymour & Weaver (1984) use the same definition of a peripheral cycle, but with a different definition of a bridge that more closely resembles the induced-cycle definition for peripheral cycles. - Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387 <a href="https://doi.org/10.1112%2Fplms%2Fs3-13.1.743" target="_blank">https://doi.org/10.1112%2Fplms%2Fs3-13.1.743</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">This is, essentially, the definition used by Bruhn (2004). However, Bruhn distinguishes the case that 
 
 
 
 G
 
 
 {\displaystyle G}
 
 has isolated vertices from disconnections caused by the removal of 
 
 
 
 C
 
 
 {\displaystyle C}
 
. - Bruhn, Henning (2004), "The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits", Journal of Combinatorial Theory, Series B, 92 (2): 235–256, doi:10.1016/j.jctb.2004.03.005, MR 2099143 <a href="https://doi.org/10.1016%2Fj.jctb.2004.03.005" target="_blank">https://doi.org/10.1016%2Fj.jctb.2004.03.005</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">See e.g. Theorem 2.4 of Tutte (1960), showing that the vertex sets of bridges are path-connected, see Seymour & Weaver (1984) for a definition of bridges using chords and connected components, and also see Di Battista et al. (1998) for a definition of bridges using equivalence classes of the binary relation on edges. - Tutte, W. T. (1960), "Convex representations of graphs", Proceedings of the London Mathematical Society, Third Series, 10: 304–320, doi:10.1112/plms/s3-10.1.304, MR 0114774 <a href="https://doi.org/10.1112%2Fplms%2Fs3-10.1.304" target="_blank">https://doi.org/10.1112%2Fplms%2Fs3-10.1.304</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Tutte (1963), Theorems 2.7 and 2.8. - Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387 <a href="https://doi.org/10.1112%2Fplms%2Fs3-13.1.743" target="_blank">https://doi.org/10.1112%2Fplms%2Fs3-13.1.743</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">See the remarks following Theorem 2.8 in Tutte (1963). As Tutte observes, this was already known to Whitney, Hassler (1932), "Non-separable and planar graphs", Transactions of the American Mathematical Society, 34 (2): 339–362, doi:10.2307/1989545, JSTOR 1989545, MR 1501641. - Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387 <a href="https://doi.org/10.1112%2Fplms%2Fs3-13.1.743" target="_blank">https://doi.org/10.1112%2Fplms%2Fs3-13.1.743</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Tutte (1963), Theorem 2.5. - Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387 <a href="https://doi.org/10.1112%2Fplms%2Fs3-13.1.743" target="_blank">https://doi.org/10.1112%2Fplms%2Fs3-13.1.743</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Bruhn, Henning (2004), "The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits", Journal of Combinatorial Theory, Series B, 92 (2): 235–256, doi:10.1016/j.jctb.2004.03.005, MR 2099143. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Thomassen, Carsten; Toft, Bjarne (1981), "Non-separating induced cycles in graphs", Journal of Combinatorial Theory, Series B, 31 (2): 199–224, doi:10.1016/S0095-8956(81)80025-1, MR 0630983. <a href="/wiki/Carsten_Thomassen_(mathematician)" target="_blank">/wiki/Carsten_Thomassen_(mathematician)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Schmidt, Jens M. (2014), "The Mondshein Sequence", Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), Lecture Notes in Computer Science, vol. 8572, pp. 967–978, doi:10.1007/978-3-662-43948-7_80, ISBN 978-3-662-43947-0. <a href="978-3-662-43947-0" target="_blank">978-3-662-43947-0</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Di Battista et al. (1998), Lemma 3.4, pp. 75–76. - Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 74–75, ISBN 978-0-13-301615-4 <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878. <a href="/wiki/Paul_Seymour_(mathematician)" target="_blank">/wiki/Paul_Seymour_(mathematician)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 74–75, ISBN 978-0-13-301615-4. <a href="978-0-13-301615-4" target="_blank">978-0-13-301615-4</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">E.g. see Borse, Y. M.; Waphare, B. N. (2008), "Vertex disjoint non-separating cycles in graphs", The Journal of the Indian Mathematical Society, New Series, 75 (1–4): 75–92 (2009), MR 2662989. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">E.g. see Cabello, Sergio; Mohar, Bojan (2007), "Finding shortest non-separating and non-contractible cycles for topologically embedded graphs", Discrete and Computational Geometry, 37 (2): 213–235, doi:10.1007/s00454-006-1292-5, MR 2295054. <a href="/wiki/Discrete_and_Computational_Geometry" target="_blank">/wiki/Discrete_and_Computational_Geometry</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Maia, Bráulio, Junior; Lemos, Manoel; Melo, Tereza R. B. (2007), "Non-separating circuits and cocircuits in matroids", Combinatorics, complexity, and chance, Oxford Lecture Ser. Math. Appl., vol. 34, Oxford: Oxford Univ. Press, pp. 162–171, doi:10.1093/acprof:oso/9780198571278.003.0010, ISBN 978-0-19-857127-8, MR 2314567{{citation}}: CS1 maint: multiple names: authors list (link). <a href="978-0-19-857127-8" target="_blank">978-0-19-857127-8</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
</ol>

Peripheral cycle open-in-new

Peripheral cycle