Peripheral cycle

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

A peripheral cycle in an undirected graph is a cycle that, informally speaking, does not separate any part of the graph from any other part. Peripheral cycles (or, as they were first called, peripheral polygons , since Tatt called cycles "polygons"), was the first to study Tatt ^[1] and they play an important role in describing planar graphs and in the formation of cyclic spaces of nonplanar graphs ^[2] .

Content

Definitions

Peripheral cycle $C$ ${\ displaystyle C}$ in the graph $G$ ${\ displaystyle G}$ can be defined formally in one of the following ways:

$C$ ${\ displaystyle C}$ is a peripheral cycle if it is a simple cycle in a connected graph with the property that for any two edges $e_{1}$ ${\ displaystyle e_ {1}}$ and $e_{2}$ ${\ displaystyle e_ {2}}$ at $G\setminus C$ ${\ displaystyle G \ setminus C}$ there is a way in $G$ ${\ displaystyle G}$ that starts at $e_{1}$ ${\ displaystyle e_ {1}}$ ends in $e_{2}$ ${\ displaystyle e_ {2}}$ and does not have internal points belonging $C$ ${\ displaystyle C}$ ^[3] .
$C$ ${\ displaystyle C}$ is a peripheral cycle if it is a generated cycle with the property that the subgraph $G\setminus C$ ${\ displaystyle G \ setminus C}$ formed by removing edges and vertices of the cycle $C$ ${\ displaystyle C}$ connected. ^[four]
If a $C$ ${\ displaystyle C}$ is any subgraph of a graph $G$ ${\ displaystyle G}$ , bridge ^[5] count $C$ ${\ displaystyle C}$ is a minimal subgraph $B$ ${\ displaystyle B}$ count $G$ ${\ displaystyle G}$ having no common edges with $C$ ${\ displaystyle C}$ and having the property that all its points of attachment (vertices adjacent to edges belonging to $B$ ${\ displaystyle B}$ and $G\setminus B$ ${\ displaystyle G \ setminus B}$ at the same time) belongs $C$ ${\ displaystyle C}$ ^[6] . Simple cycle $C$ ${\ displaystyle C}$ is peripheral if it has exactly one bridge ^[7]

It is easy to see the equivalence of these definitions: a connected subgraph of a graph $G\setminus C$ ${\ displaystyle G \ setminus C}$ (along with the ribs connecting it with $C$ ${\ displaystyle C}$ ) or a chord of a cycle that violates the generation of the cycle, in any case, must be a bridge and there must also be an equivalence class of binary relations on edges in which two edges are connected if they are ends of the path without internal vertices in $C$ ${\ displaystyle C}$ ^[eight]

Properties

Peripheral cycles appear in the theory of polyhedral graphs , that is, vertex 3-connected planar graphs . For any planar graph $G$ ${\ displaystyle G}$ and any planar investment $G$ ${\ displaystyle G}$ the edges of the nesting generated by the cycles must be peripheral cycles. In a polyhedral graph, all faces are peripheral cycles and any peripheral cycle is a face ^[9] . It follows that (to combinatorial equivalence, the choice of the outer face and the orientation of the plane) any polyhedral graph has a unique planar embedding ^[10] .

In planar graphs, a formed by faces, but in nonplanar graphs, peripheral cycles play a similar role - for any vertex 3-connected finite graph, a cyclic space is formed by peripheral cycles ^[11] . The result can be extended to locally finite infinite graphs ^[12] . In particular, it follows that 3-connected graphs are guaranteed to contain peripheral cycles. There are 2-connected graphs that do not contain peripheral cycles (an example is a complete bipartite graph $K_{2,4}$ ${\ displaystyle K_ {2,4}}$ , in which any cycle has two bridges), but if a 2-connected graph has a minimum degree of three, then it contains at least one peripheral cycle ^[13] .

The peripheral cycles in 3-connected graphs can be calculated in linear time and used to develop planarity tests ^[14] . They have also been expanded to the more general notion of non-dividing ear expansions. In some algorithms, to check the planarity of graphs, it is useful to find a cycle that is not peripheral in order to divide the task into smaller subtasks. In a doubly connected graph with a contour rank of less than three (such as a cycle or a theta graph ), any cycle is peripheral, but any doubly connected graph with a contour rank of three or more has a non-peripheral cycle that can be found in linear time ^[15] .

Summarizing chordal graphs , Seymour and Weaver ^[16] defined a compressed graph as a graph in which any peripheral cycle is a triangle. They described these graphs as clique sums of chordal graphs and maximal planar graphs ^[17] .

Related Concepts

Peripheral cycles were also called non-separating cycles ^[3] , but this term is ambiguous, because it is also used for two other concepts - for simple cycles, the removal of which makes the remaining graph disconnected ^[18] , and cycles of topological embedding of the graph such that cutting along the cycle is not makes a disconnected surface into which the graph is embedded ^[19] .

In matroids , a non-dividing cycle is a matroid cycle (that is, a minimal dependent set) such that cycle leaves a smaller matroid that is connected (that is, which cannot be split into a direct sum of matroids) ^[20] . They are similar to peripheral cycles, but not the same even in (matroids in which cycles are simple graph cycles). For example, in a full bipartite graph $K_{2,3}$ ${\ displaystyle K_ {2,3}}$ any cycle is peripheral (it has only one bridge, a path of two edges), but the graph matroid formed by this bridge is not connected, so there is no cycle of the graph matroid of the graph $K_{2,3}$ ${\ displaystyle K_ {2,3}}$ not non-separating.

Notes

↑ Tutte, 1963 .
↑ Tutte, 1963 , p. 743-767.
↑ ¹ ² Di Battista, Eades, Tamassia, Tollis, 1998 , p. 74–75.
↑ This is the definition used by Brun ( Bruhn 2004 ). However, Brun distinguished the case that $G$ ${\ displaystyle G}$ has isolated vertices from incoherence caused by loop removal $C$ ${\ displaystyle C}$ .
↑ Not to be confused with a bridge , another concept with the same name.
↑ Tutte, 1960 , p. 304-320.
↑ This definition of peripheral cycles was originally used by Tutt. Seymour and Weaver used the same definition of a peripheral cycle, but with a different definition of a bridge, which closely resembles the definition of generated cycles for peripheral cycles.
↑ See, for example, Theorem 2.4 in an article by Tutte ( 1960 ) showing that multiple bridge tops are connected by paths; see Seymour and Weaver 1984 for defining bridges using chords and connected components, as well as Di Battista, Eades, Tamassia, Tollis 1998 ) for defining bridges using the binary relation equivalence classes on edges.
↑ Tutte, 1963 , p. Theorems 2.7 and 2.8.
↑ See the remarks after Theorem 2.8 in Tutte's paper ( Tutte 1963 ). As Tutt notes, this was already known to Whitney ( Whitney 1932 )
↑ Tutte, 1963 , p. Theorem 2.5.
↑ Bruhn, 2004 , p. 235–256.
↑ Thomassen, Toft, 1981 , p. 199-224.
↑ Schmidt, 2014 , p. 967-978.
↑ Di Battista, Eades, Tamassia, Tollis, 1998 , p. 75–76 Lemma 3.4.
↑ Seymour, Weaver, 1984 .
↑ Seymour, Weaver, 1984 , p. 241–251.
↑ See, for example, ( Borse, Waphare 2008 )
↑ See, for example ( Cabello, Mohar 2007 )
↑ Maia, Lemos, Melo, 2007 , p. 162–171.

Literature

Tutte WT How to draw a graph // Proceedings of the London Mathematical Society. - 1963.- T. 13 . - S. 743-767 . - DOI : 10.1112 / plms / s3-13.1.743 .
Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. - Prentice Hall , 1998. - S. 74–75. - ISBN 978-0-13-301615-4 .
Tutte WT Convex representations of graphs // Proceedings of the London Mathematical Society. - 1960 .-- T. 10 . - S. 304-320 . - DOI : 10.1112 / plms / s3-10.1.304 .
Hassler Whitney Non-separable and planar graphs // Transactions of the American Mathematical Society. - 1932. - T. 34 , no. 2 . - S. 339-362 . - DOI : 10.2307 / 1989545 .
Henning Bruhn. The cycle space of a 3-connected locally finite graph is generated by its finite and infinite peripheral circuits // Journal of Combinatorial Theory. - 2004 .-- T. 92 , no. 2 . - S. 235–256 . - DOI : 10.1016 / j.jctb.2004.03.03.005 .
Carsten Thomassen, Bjarne Toft. Non-separating induced cycles in graphs // Journal of Combinatorial Theory. - 1981. - T. 31 , no. 2 . - S. 199–224 . - DOI : 10.1016 / S0095-8956 (81) 80025-1 .
Jens M. Schmidt. The Mondshein Sequence // Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14). - 2014 .-- S. 967-978. - DOI : 10.1007 / 978-3-662-43948-7_80 .
Seymour PD, Weaver RW A generalization of chordal graphs // Journal of Graph Theory. - 1984. - T. 8 , no. 2 . - S. 241–251 . - DOI : 10.1002 / jgt.3190080206 .
Borse YM, Waphare BN Vertex disjoint non-separating cycles in graphs // The Journal of the Indian Mathematical Society. - 2008. - T. 75 , no. 1-4 . - S. 75–92 (2009) .
Sergio Cabello, Bojan Mohar. Finding shortest non-separating and non-contractible cycles for topologically embedded graphs // Discrete and Computational Geometry . - 2007.- T. 37 , no. 2 . - S. 213–235 . - DOI : 10.1007 / s00454-006-1292-5 .
Bráulio Maia Junior, Manoel Lemos, Tereza RB Melo. Non-separating circuits and cocircuits in matroids // Combinatorics, complexity, and chance. - Oxford: Oxford Univ. Press, 2007. - T. 34. - S. 162–171. - (Oxford Lecture Ser. Math. Appl.). - DOI : 10.1093 / acprof: oso / 9780198571278.003.0010 .

[_19f6b7e35ec8d58a-1] Tutte, 1963 .

[_a406cfc05ea2265b-2] Tutte, 1963 , p. 743-767.

[_1548095faae1dfaf-3] ¹ ² Di Battista, Eades, Tamassia, Tollis, 1998 , p. 74–75.

[4] This is the definition used by Brun ( Bruhn 2004 ). However, Brun distinguished the case that $G$ ${\ displaystyle G}$ has isolated vertices from incoherence caused by loop removal $C$ ${\ displaystyle C}$ .

[5] Not to be confused with a bridge , another concept with the same name.

[_1385eda218233dd6-6] Tutte, 1960 , p. 304-320.

[7] This definition of peripheral cycles was originally used by Tutt. Seymour and Weaver used the same definition of a peripheral cycle, but with a different definition of a bridge, which closely resembles the definition of generated cycles for peripheral cycles.

[8] See, for example, Theorem 2.4 in an article by Tutte ( 1960 ) showing that multiple bridge tops are connected by paths; see Seymour and Weaver 1984 for defining bridges using chords and connected components, as well as Di Battista, Eades, Tamassia, Tollis 1998 ) for defining bridges using the binary relation equivalence classes on edges.

[_9e10d6ce3fe42256-9] Tutte, 1963 , p. Theorems 2.7 and 2.8.

[10] See the remarks after Theorem 2.8 in Tutte's paper ( Tutte 1963 ). As Tutt notes, this was already known to Whitney ( Whitney 1932 )

[_3f10ccc8a02307db-11] Tutte, 1963 , p. Theorem 2.5.

[_7dc2d7ab1212663a-12] Bruhn, 2004 , p. 235–256.

[_46714f8b99d3598f-13] Thomassen, Toft, 1981 , p. 199-224.

[_d9b8e6c9981be9e4-14] Schmidt, 2014 , p. 967-978.

[_a025417fca7ae96e-15] Di Battista, Eades, Tamassia, Tollis, 1998 , p. 75–76 Lemma 3.4.

[_e83f3e17cf781979-16] Seymour, Weaver, 1984 .

[_90351c5c9c5fa3e7-17] Seymour, Weaver, 1984 , p. 241–251.

[18] See, for example, ( Borse, Waphare 2008 )

[19] See, for example ( Cabello, Mohar 2007 )

[_b61a977c3e842474-20] Maia, Lemos, Melo, 2007 , p. 162–171.