betaFeedback

WorksMathematics

An approximate cactus-decomposition for vertex-connectivity

Abstract

The classical cactus theorem of Dinitz, Karzanov and Lomonosov from 1976 states that the minimum edge-cuts of a connected graph are displayed by a cactus. For vertex-separations, Tutte's theorem gives an exact cactus-decomposition for connectivity 22, but exact cactus-decompositions fail for higher connectivity. Extending earlier approximate cactus-decomposition results for connectivities 33 and 44 by Carmesin and Kurkofka [FOCS 2023] and Kurkofka and Planken [SODA 2026] to all connectivities, we prove that for every k∈Nk\in\mathbb{N} there is a constant d=d(k)d=d(k) such that every kk-connected graph GG admits a cactus-decomposition displaying kk-separations such that every kk-separation of GG has edit-distance at most dd to a displayed separation. Our proof develops tools that may be useful beyond this result. The first is a three-dimensional version of the classical corner-diagram method, which we use to show that triples of crossing kk-separations have a controlled two-dimensional behaviour. The second is a covering-space approach for studying local crossing patterns from a global perspective. Third, we advance the theory of flowers, which originated in matroid theory.

AI methodology: § 15.

Introduction

The classical cactus theorem of Dinitz, Karzanov, and Lomonosov from 1976 [48] says that the set of minimum edge-cuts of every connected graph has the structure of a cactus1. The DKL cactus representation can be computed in near-linear time [69], and hence can be used to enumerate all minimum cuts efficiently [KP09, LST21]. It is a key ingredient in algorithms for connectivity augmentation [Gab16, NGM97, CLP22] and for maintaining minimum cuts under edge insertions [Hen97, DW98, GHT18]. Vertex-connectivity encompasses edge-connectivity as a special case via the line-graph construction. However, the direct extension of the cactus theorem to arbitrary vertex-connectivity fails. The connection between vertex-connectivity and tree-decompositions makes this question particularly relevant for algorithmic applications.

The quest for such an analogue goes back at least to Tutte’s seminal work from 1966 [Tut66], even predating the DKL theorem. The search for a cactus-type representation of minimum vertex-separations2 motivated the work of Cohen, Di Battista, Kanevsky, and Tamassia [21] and subsequent structural and algorithmic investigations [91, 106, 112]. The broader problem of decomposing a kk-connected3 graph into (k+1)(k+1)-connected regions has been intensively studied in the last decade [25, 65 Erd17, 42, 7]. These results reveal substantially richer interactions between minimum vertex-separations than between minimum edge-cuts, making the formulation of a suitable global representation a challenge in its own right. In this paper, we establish an approximate cactus-decomposition theorem for arbitrary vertex-connectivity.

Our starting point is the SPQR decomposition – the algorithmic counterpart of Tutte’s 2-separator theorem – in the cactus-formulation of [EP14]. Informally, a cactus-decomposition of a graph GG is defined like a tree-decomposition, except that the decomposition tree is replaced by a strong cactus CC, some of whose nodes are designated as ‘PP-nodes’. The decomposition displays separations of GG through four types of cuts of CC: a bridge, two edges on a common cycle, a cut consisting of edges incident with a single PP-node, or the empty cut4; see Figure 1.1. Each such cut defines a bipartition of the nodes of CC, which we pull back to a separation of GG by taking the union of the bags on each side. The resulting separation is displayed by the cactus-decomposition; see § 3.4 for the formal definitions. Cactus-decompositions extend the tree structure of nested separations in the simplest way, by allowing cycles to accommodate coherent crossings. The SPQR theorem is implied5 by the following variant [EP14]: Every 2-connected graph has a cactus-decomposition displaying all its proper 2-separations.

Figure 1.1. A 2-connected graph (black) and a cactus-decomposition (red), with each cactus node at the centre of its corresponding blue bag and the PP-nodes drawn in yellow. Deleting a bridge or two edges of a common cycle splits the cactus into two components; the unions of their bags form the two sides of a displayed separation. The bags of the PP-nodes, circled in green, form correspond to 2-separators whose deletion leaves more than two components: these may be partitioned arbitrarily into two groups, with the separator included on both sides. The cycles of the cactus encode the crossing patterns of minimum cuts, while the bridges encode the cuts that avoid every crossing.

SPQR trees have become a standard algorithmic tool, underlying classical algorithms for planarity testing and planar embeddings [71, 100], planar graph isomorphism [70, 72], and dynamic connectivity and planarity problems [21, 39, 40].

For higher vertex-connectivity, exact cactus-decompositions are no longer possible in general: some graphs admit no cactus-decomposition simultaneously displaying all their minimum-order separations; this happens already for 3-separations, see [32] for a detailed discussion. For general kk, cylindrical grids, such as the one in Figure 1.2, provide examples of obstructions to an exact cactus-decomposition in which the necessary approximation error grows with kk. Despite the linear global structure of these graphs, their kk-separations admit too much local freedom to all be displayed by a single cactus-decomposition.

Figure 1.2. A 6-connected graph obtained from a cylindrical grid by adding both diagonals in alternate faces and attaching a large clique at each end. The top and bottom rows are identified. The three coloured separations pairwise cross. They cannot be displayed at a common PP-node, since their separators are distinct, or on a common cycle, since each separator meets all four corners of the other two. Thus no cactus-decomposition displays all the 6-separations of this graph.

To address this for k=3k = 3, Carmesin and Kurkofka [32] introduced tri-separations, modified versions of 3-separations that retain their separating properties while removing the local ambiguity that prevents an exact cactus-decomposition. With this, they obtained a Tutte-type decomposition of 3-connected graphs. Kurkofka and Planken [84] subsequently introduced tetra-separations and proved a Tutte-type decomposition theorem for 4-connected graphs. These exact results for modified notions of separation can be viewed as approximate cactus-decomposition theorems for ordinary vertex-separations: for k=3,4k = 3, 4, every large enough kk-connected graph GG admits a cactus-decomposition displaying kk-separations such that every kk-separation of GG has edit-distance at most kk to a displayed kk-separation; here, the edit-distance between separations (A,B)(A, B) and (C,D)(C, D) is measured by max⁡{∣A△C∣,∣B△D∣}\max\{ |A \mathbin{\triangle} C|, |B \mathbin{\triangle} D| \}.

Our main result generalizes this approximate cactus picture to arbitrary vertex-connectivity:

Theorem 1.1 (Simplified version for kk-connected graphs). For every k∈Nk \in\mathbb{N}, there is d∈Nd \in\mathbb{N} such that every kk-connected graph GG admits a cactus-decomposition displaying kk-separations such that every kk-separation of GG has edit-distance at most dd to a displayed separation.

A graph can have quadratically many distinct separators of minimum size [78], and a single separator can give rise to exponentially many separations. For fixed kk, our theorem gives a linear-size data structure that approximately represents all kk-separations of a kk-connected graph. These are represented implicitly by the cactus and its bags through bridges, cycles and PP-nodes. Compact representations of minimum vertex separations have also been studied in connection with pairwise connectivity queries [KTDBC91, CDBKT93, PY21]; see § 2.3.

Unbreakability is a standard relaxation of the notion of connectivity in parameterized algorithms, introduced in the context of recursive understanding [92, 20 LRSZ18, 35], which reduces many graph problems to suitable unbreakable instances. In this paper, we prove a strengthening of Theorem 1.1 with the assumption of ‘kk-connectivity’ relaxed to ‘(k−1)(k-1)-unbreakability’. This generalisation allows us to apply our result iteratively.

Formally, a graph is (q,k)(q,k)-unbreakable if every separation of order at most kk has a proper side of size at most qq. Thus, the kk-connected graphs are exactly the (0,k−1)(0,k-1)-unbreakable graphs with more than kk vertices, while allowing q>0q>0 gives an approximate version of kk-connectivity. This relaxation allows us to look beyond the local obstructions imposed by low-degree vertices and capture the global connectivity of graphs such as square grids and cubic expanders. Our main result holds in this more general setting:

Theorem 1.2 (Main theorem). For all q,k∈Nq,k \in\mathbb{N}, there is d∈Nd \in\mathbb{N} such that every (q,k−1)(q,k-1)-unbreakable graph GG admits a cactus-decomposition displaying (≤k)(\le k)-separations such that every (≤k)(\le k)-separation of GG has edit-distance at most dd to a displayed separation.

The approximation bound dd is effective and can be taken to be 2(q+k)O(1)2^{(q+k)^{O(1)}}. We leave the dependence on qq and kk implicit in our proof, prioritising simplicity over optimizing bounds.

Iterated decompositions have proved useful in structural graph theory [30], graph enumeration [GNR13], and algorithms for connectivity [47, 37] and graph isomorphism [DNTW10, DLN+22]. Theorem 1.2 can be applied recursively as follows. We first group together the bags whose nodes lie on the same cycle of the cactus, obtaining pieces with cycle-decompositions of bounded adhesion. We retain these cyclic pieces, as well as the bags at PP-nodes (which have size at most kk). Each remaining bag can be described by a kk-unbreakable minor of GG, to which we apply Theorem 1.2 with kk increased by one to reveal finer structure, see Section A.

Examples and the need for approximation

We now illustrate our theorem on a few families of graphs with a simple underlying structure, showing how the cactus-decomposition can recover this structure. Some of these examples also justify the need for approximation.

Already for k=3,4k = 3, 4, there are kk-connected graphs whose kk-separations cannot all be displayed by a single cactus-decomposition. Toroidal hexagonal and square grids provide examples for k=3k = 3 and k=4k = 4, respectively. These examples extend to higher connectivity, for instance by adding universal vertices, or by replacing each vertex vv by a clique K(v)K(v) and replacing each edge uwuw with all possible edges between K(u)K(u) and K(w)K(w). However, these graphs are (q,k)(q, k)-unbreakable for some qq depending only on kk, so every kk-separation has a side of bounded size. It is therefore natural to accept such graphs as basic pieces of our decomposition, leaving them intact and focusing on sufficiently broad separations, meaning those with both sides sufficiently large.

To see why even these separations require approximation, consider a long cylindrical grid of width kk, with a large clique attached at each end; see Figure 1.3. This graph is (q,k−1)(q, k-1)-unbreakable for some qq depending only on kk. Its vertical cross-sections define separations of order kk. These separations admit local modifications that preserve their order but produce crossing patterns that cannot all be displayed by a single cactus-decomposition, for the same reason as in Figure 1.2. Since the end cliques can be arbitrarily large, all the separations involved can be arbitrarily broad.

Figure 1.3. Both panels show a cylindrical grid of width 6, with the top and bottom rows identified. Left: the red 6-separation is close to the blue separation defined by a single vertical cross-section. Right: in the 7th power of the grid, the red vertices form a minimum separator. The corresponding separation is close to the blue separation, whose separator consists of seven consecutive cross-sections.

Nevertheless, as illustrated in Figure 1.3, every sufficiently broad kk-separation differs from a straight one only on a number of vertices bounded in terms of kk, independently of the length of the cylinder. The cactus-decomposition constructed in our proof displays precisely the straight separations, thereby recovering the intrinsic linear structure of the graph.

Taking the rr-th power of this graph yields a k′k'-connected example with k′=rkk' = rk, provided r≥kr \ge k and the end cliques are sufficiently large. Now, the vertices of any rr consecutive vertical cross-sections form a minimum separator. The cactus-decomposition constructed in our proof displays precisely these separations, again recovering the intrinsic linear structure of the graph. More generally, as illustrated in Figure 1.3, a minimum separator consists of rr consecutive vertices on each longitudinal path, with starting positions differing by at most one between neighbouring paths. These variable bands give rise to the same obstruction to an exact cactus representation, now among minimum-order separations of a k′k'-connected graph. Thus, strengthening unbreakability to kk-connectivity does not eliminate the obstruction. Nevertheless, every minimum separation still differs from one displayed by our decomposition only on a bounded number of vertices.

One might hope to recover an exact theorem by generalising tri- and tetra-separations to a suitable notion of reduced mixed-separation, whose separator may contain both vertices and edges. In the cylinder examples, however, the crossing patterns can involve a number of vertices quadratic in the width of the cylinder, and it is not clear how a reduction favouring edges over vertices could resolve them.

A toroidal grid whose longitude is much longer than its meridian provides a cyclic analogue of the cylinder; see Figure 1.4. Writing mm for the length of the meridian and setting k=2mk = 2m, this graph is again (q,k−1)(q, k - 1)-unbreakable for some qq depending only on kk. Pairs of meridional cross-sections define separations of order kk, and every sufficiently broad kk-separation differs from one of these only on a bounded number of vertices, as shown in Figure 1.4. Our construction displays precisely the separations defined by these pairs of cross-sections, thereby recovering the intrinsic cyclic structure of the graph.

Figure 1.4. A toroidal grid with meridians of length m=16m = 16 and longitudes of length 40, so k=2m=32k = 2m = 32. The two blue meridians together form the separator of a kk-separation. The red cycles together form the separator of another kk-separation, whose sides agree with those of the blue one outside the two separators.

Finally, consider the following generalisation of the wheels introduced by Geelen and Joeris [62]. Take a long cyclic sequence of arbitrary tt-vertex trees, join consecutive trees by arbitrary perfect matchings, and add ℓ\ell hubs, each adjacent to a vertex in every tree; see Figure 1.5 for an example. For k=2t+ℓk = 2t + \ell, these graphs are again (q,k−1)(q, k - 1)-unbreakable for some qq depending only on kk. Pairs of trees together with all the hubs define separations of order kk. Every sufficiently broad kk-separation differs from one of these only on a number of vertices bounded in terms of kk. Our cactus-decomposition recovers the cyclic arrangement of the trees, with the hubs forming a common core of the displayed separators.

Figure 1.5. Twelve trees with t=4t = 4 vertices each, joined cyclically by perfect matchings, and ℓ=2\ell= 2 hubs, so k=2t+ℓ=10k = 2t + \ell= 10. The two blue trees and the hubs form the separator of a kk-separation. The red vertices and the hubs form the separator of another kk-separation, whose sides agree with those of the blue one outside the two separators.

A short outline of the proof of Theorem 1.1 (see Section 2 for a detailed overview).

We construct the cactus-decomposition of Theorem 1.1 in two steps. First, we build a tree-decomposition T\mathcal{T} whose bags, roughly speaking, either have higher connectivity or possess a cyclic or star-like structure. We then refine T\mathcal{T} into the desired cactus-decomposition C\mathcal{C} by replacing each bag of the latter type with the corresponding cycle or star-decomposition, with the centres of the stars becoming PP-nodes.

Step 1: Constructing the tree-decomposition T\mathcal{T}. We construct our tree-decomposition from a maximal nested set of carefully selected separations and use maximality to obtain the desired approximation guarantee. A maximality argument also underlies a modern proof of the tangle-tree theorem [Car16], where the aim is to distinguish the highly connected regions of a graph GG, formalised by its maximal tangles. We briefly recall the argument. Given a graph GG, let SS be the set of all separations efficiently distinguishing two tangles, and choose a maximal nested subset T⊆S\mathcal{T} \subseteq S. The separations in T\mathcal{T} induce a tree-decomposition T\mathcal{T}: since they are nested, we can successively split GG along them to obtain the bags of the decomposition. One then shows that the maximality of T\mathcal{T} ensures that T\mathcal{T} distinguishes all maximal tangles.

We now return to the proof of Theorem 1.1 and explain how we use maximality in this setting. Given k∈Nk \in\mathbb{N}, choose constants β\beta and γ\gamma depending only on kk; their precise values are not important for this overview. The approximation bound dd will be larger than both.

Let GG be a kk-connected graph. We say that two kk-separations (A,B)(A, B) and (C,D)(C, D) heavily cross if all four sets A∩CA \cap C, A∩DA \cap D, B∩CB \cap C and B∩DB \cap D have size at least γ\gamma. Intuitively, these are the separations that will be captured by the cyclic parts of the cactus, so we set them aside in the first step. Let SS be the set of all kk-separations (A,B)(A, B) with ∣A∣,∣B∣≥β|A|, |B| \ge\beta that are not heavily crossed. Choose a maximal nested subset T⊆S\mathcal{T} \subseteq S, and let T\mathcal{T} be the tree-decomposition induced by T\mathcal{T}.

Using corner diagram arguments, we show that every separation in SS has bounded edit-distance to some separation in T\mathcal{T}. Thus, T\mathcal{T} approximately displays all separations in SS. Separations (A,B)(A, B) with ∣A∣<β|A| < \beta or ∣B∣<β|B| < \beta are already within edit-distance β\beta of (∅,V(G))(\varnothing, V(G)) or (V(G),∅)(V(G), \varnothing), respectively, and are therefore covered by our choice of dd. It remains to refine T\mathcal{T} into a cactus-decomposition that also approximately displays the heavily crossed separations.

Construction of the cactus-decomposition C\mathcal{C}

Step 2: Construction of the cactus-decomposition C\mathcal{C}. We say that a separation (A,B)(A,B) lives in a bag of a tree-decomposition if its separator is contained in that bag. Another corner diagram argument shows that every heavily crossed kk-separation has bounded edit-distance to a separation that lives in a bag of T\mathcal{T} and remains heavily crossed (for a slightly smaller value of γ\gamma).

We can therefore build C\mathcal{C} by treating the bags of T\mathcal{T} separately. For each bag, we seek a cycle- or star-decomposition of its torso that approximately displays all the heavily crossed kk-separations living there. Here, the torso is the graph induced by the bag, with each intersection with a neighbouring bag completed to a clique. Constructing these local decompositions is the heart of the proof and relies on the following new ideas:

  1. Each separation (A,B)(A,B) partitions the vertex set into three parts: A∖BA \setminus B, A∩BA \cap B and B∖AB \setminus A. Three separations therefore determine 27 regions. We show that when three kk-separations pairwise heavily cross, their crossing pattern is much more constrained: many of these regions must be empty, and the whole configuration admits a cyclic description. In particular, heavily crossing separations cannot form truly three-dimensional crossing patterns, such as the one in Figure 1.6.

Figure 1.6. Three separations cross three-dimensionally in the line-graph of the cube. Their separators are indicated in red, green and blue.

  1. Families of separations with a common separator can be displayed by a star-decomposition. For the cyclic case, we use ideas from covering spaces in topology to combine the cyclic descriptions of triples in (i) into a single cycle-decomposition that approximately displays the family. Such cycle- and star-decompositions correspond to flowers from the matroid literature [105, 11]; Figure 1.7 illustrates the cyclic case.

Figure 1.7. A cycle-decomposition (blue bags, red decomposition cycle) of a graph GG (black) that is a 4-flower

  1. Several crossing families may occur in the same bag of T\mathcal{T}, giving rise to several flowers. However, by choosing dd sufficiently large compared to β\beta and γ\gamma, we show that one flower per bag suffices: we can select a flower F\mathcal{F} in each bag so that every kk-separation living in this bag is within bounded edit-distance of a separation displayed by F\mathcal{F} or T\mathcal{T}. This requires a

systematic analysis of flowers which, together with the canonical constructions via coverings in (ii), extends the structural theory of flowers in graphs, and provides, for the first time, canonical constructions of flowers.

This completes the second step of the construction and thus our brief proof overview. We give a more detailed proof overview in Section 2, expanding on each of these three ideas.

A brief real-world example with a cyclic structure

Figure 1.8 shows an eight-petal flower in a contact graph obtained from the human nuclear-pore model PDB 7TBJ of Petrovic et al. [109].

Figure 1.8. An eight-petal flower in a biological contact graph. Left: the largest component of the contact graph of the human nuclear-pore model PDB 7TBJ (Petrovic et al.). Vertices represent protein fragments; edges record contacts within 55 Å between non-hydrogen atoms. Vertex positions are obtained by projecting the fragment centres onto the xyxy-plane, so distinct vertices may overlap in the drawing. In particular, the six red vertices form a separator. This is difficult to discern in the projected drawing at the displayed scale, but becomes clear at 400% magnification. Right: the eight bags form a cycle with three-vertex overlaps; matching colours identify their interiors on the left. The red 6-separator leaves 469 vertices on each exclusive side.

Improving the constants in our main theorem would be interesting: with bounds small enough to apply here, an iterative application might eventually look like this: the graph has a unique 6-tangle that, for every separation (A,B)(A, B) of order at most five, selects a side containing a vertex from each of the eight coloured petal interiors outside A∩BA \cap B. We would start to decompose iteratively with the block-cutvertex theorem, Tutte’s theorem at every 2-block and then the tri-separator theorem at each 3-connected torso, etc. Eventually, we would obtain a 5-unbreakable minor carrying this 6-tangle. Then we would apply the cactus decomposition for k=6k = 6, and the cactus structure it would compute would be similar to the cyclic decomposition of Figure 1.8. The underlying computations have been worked out in detail, see [29].

Applications and perspectives

Tangles and flowers. A tangle describes a highly connected region of a graph by indicating, for each separation of small order, on which side it lies. The tangle-tree theorem provides a tree-decomposition that distinguishes these regions [115]. We would like to extend this viewpoint to include large flowers as highly connected regions in a broader sense. This leads us to consider bramble orientations, a relaxation of tangles, and to group related orientations describing the same flower. We seek an analogue of the tangle-tree theorem that recognises these flower regions and distinguishes them from one another and from tangles. In a follow-up paper [13], we build on the structural results developed here to obtain an approximate tangle-tree theorem that also detects sufficiently large flowers.

Connectivity augmentation. The Connectivity Augmentation problem asks whether a graph can be made kk-connected by adding at most ℓ\ell edges from a prescribed set. If the graph is already (k−1)(k-1)-connected, this amounts to selecting edges that cross every proper (k−1)(k-1)-separation. For edge-connectivity, the DKL theorem reduces increasing the connectivity by one to augmentation on a cactus. This reduction has led to FPT and approximation algorithms for minimum-cost augmentation [101, 124].

For vertex-connectivity, Carmesin and Ramanujan [37] obtained FPT algorithms parameterized by ℓ\ell for k≤4k \le4, using exact cactus representations. Korhonen and Thorup [93] extended this result to arbitrary kk with running time 2O(ℓlog⁡(ℓ+k))nO(1)2^{O(\ell\log(\ell+k))}n^{O(1)}, using approximate structural arguments. For k=2k=2, Koana and Kumabe [80] recently obtained an FPT algorithm with single-exponential dependence on ℓ\ell for arbitrary input graphs. A natural question is whether our approximate cactus representation can help achieve such a dependence on ℓ\ell for larger fixed kk.

Canonicity and symmetry. The canonicity of the Tutte-decomposition underlies linear-time and logspace algorithms for planar graph isomorphism [72, 49]. Retaining cyclic torsos matters for canonicity: decomposing a long cycle into bounded-size bags necessarily breaks some of its symmetries [LPPS22]. The decomposition in Theorem 1.2 approximately represents the full family of separations of small order, which is canonical. Its displayed separation system is therefore preserved by every automorphism up to bounded edit-distance, yielding a form of approximate canonicity.

Since canonical decompositions are invariant under graph automorphisms, they are particularly useful for studying highly symmetric graphs. Using their canonical tetra-decomposition [84], Kurkofka and Planken classified all finite connected vertex-transitive graphs of connectivity below five [83]. Our decomposition may help extend their classification to higher connectivity.

Cops and robber. In the classical helicopter cops and robber game, kk cops win precisely when the graph has treewidth less than kk [121]. Consider the randomized variant with an invisible robber, no repeated visits by the cops, and mixed strategies6 for both players. For k≤4k \le4, Planken [107] uses the corresponding cactus-decomposition theorems to determine the maximum winning probability of kk cops on kk-connected graphs. Our cactus representation may support similar analyses at higher connectivity.

Local analogues. Local separators disconnect bounded-radius balls without necessarily separating the whole graph. Local analogues of graph decomposition theorems have been developed in [19, 18, 46, 76]. This perspective has also led to structural characterizations and canonical decompositions of locally chordal graphs [5, 6, 75]. Local separators have applications in network analysis [27] and distributed approximation [15].

Our construction of the cyclic parts of the decomposition uses covering graphs to combine local separators into global separators. This suggests a local analogue of our theorem that, under appropriate local connectivity assumptions, approximately represents local separations together with their crossing structure.

Related work

References

  1. [1]Kiyoshi Ando, Yoshimi Egawa, Ken-ichi Kawarabayashi, and Matthias Kriesell. On the number of 4-contractible edges in 4-connected graphs. Journal of Combinatorial Theory, Series B, 99(1):97–109, 2009. doi:10.1016/j.jctb.2008.04.003.DOI
  2. [2]Kiyoshi Ando, Hikoe Enomoto, and Akira Saito. Contractible edges in 3-connected graphs. Journal of Combinatorial Theory, Series B, 42(1):87–93, 1987. doi:10.1016/0095-8956(87)90065-7.DOI
  3. [3]Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. In Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA ’08, pages 641–650, 2008. URL: https://dl.acm.org/doi/10.5555/1347082.1347153.
  4. [4]Elad Aigner-Horev, Reinhard Diestel, and Luke Postle. The structure of 2-separations of infinite matroids. Journal of Combinatorial Theory, Series B, 116:25–56, 2016. doi:10.1016/j.jctb.2015.05.011.
  5. [5]Tara Abrishami and Paul Knappe. The global structure of locally chordal graphs, 2025. arXiv:2512.19044.arxiv.org/abs/2512.19044
  6. [6]Tara Abrishami, Paul Knappe, and Jonas Kobler. Locally chordal graphs, 2025. arXiv:2501.17320v2.arxiv.org/abs/2501.17320
  7. [7]Sandra Albrechtsen. Refining trees of tangles in abstract separation systems: Inessential parts. Combinatorial Theory, 4(1):# 17, 2024. doi:10.5070/C64163854.DOI
  8. [8]Sandra Albrechtsen. Refining tree-decompositions so that they display the k-blocks. Journal of Graph Theory, 109(3):310–314, 2025. doi:10.1002/jgt.23230.DOI
  9. [9]Sandra Albrechtsen. Optimal trees of tangles: refining the essential parts. Innovations in Graph Theory, 3:171–206, 2026. doi:10.5802/igt.21.DOI
  10. [10]Aditya Anand, Euiwoong Lee, Jason Li, Yaowei Long, and Thatchaphol Saranurak. Unbreakable decomposition in close-to-linear time. In Proceedings of the 2025 Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 1464–1493. SIAM, 2025. doi:10.1137/1.9781611978322.46.DOI
  11. [11]Jeremy Aikin and James Oxley. The structure of crossing separations in matroids. Advances in Applied Mathematics, 41(1):10–26, 2008. doi:10.1016/j.aam.2007.05.004.DOI
  12. [12]Jeremy Aikin and James Oxley. The structure of the 4-separations in 4-connected matroids. Advances in Applied Mathematics, 48(1):1–24, 2012. doi:10.1016/j.aam.2011.06.001.DOI
  13. [13]Romain Bourneuf, Johannes Carmesin, Jan Kurkofka, and Tim Planken. Turning brambles into flowers. In preparation, 2026.
  14. [14]Nathan Bowler, Florian Gut, Meike Hatzel, Ken-ichi Kawarabayashi, Irene Muzi, and Florian Reich. Decomposition of (infinite) digraphs along directed 1-separations, 2023. arXiv:2305.09192.arxiv.org/abs/2305.09192
  15. [15]Marthe Bonamy, Cyril Gavoille, Timothé Picavet, and Alexandra Wesolek. Local constant approximation for dominating set on graphs excluding large minors. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 77–87, New York, NY, USA, 2025. doi:10.1145/3732772.3733531.DOI
  16. [16]Nick Brettell, Susan Jowett, James Oxley, Charles Semple, and Geoff Whittle. What is a 4-connected matroid? The Electronic Journal of Combinatorics, 32(2):P2.1, 2025. doi:10.37236/12467.DOI
  17. [18]Johannes Carmesin. Local k-separators, 2021. Manuscript.
  18. [19]Johannes Carmesin. Local 2-separators. Journal of Combinatorial Theory, Series B, 156:101–144, 2022. doi:10.1016/j.jctb.2022.04.005.DOI
  19. [20]Rajesh Chitnis, Marek Cygan, MohammadTaghi Hajiaghayi, Marcin Pilipczuk, and Michał Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. SIAM Journal on Computing, 45(4):1171–1229, 2016. doi:10.1137/15M1032077.DOI
  20. [21]Robert F. Cohen, Giuseppe Di Battista, Arkady Kanevsky, and Roberto Tamassia. Reinventing the wheel: an optimal data structure for connectivity queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, pages 194–200, New York, NY, USA, 1993. doi:10.1145/167088.167152.DOI
  21. [22]Johannes Carmesin, Reinhard Diestel, Matthias Hamann, and Fabian Hundertmark. k-blocks: A connectivity invariant for graphs. SIAM Journal on Discrete Mathematics, 28(4):1876–1891, 2014. doi:10.1137/130923646.DOI
  22. [23]Johannes Carmesin, Reinhard Diestel, Matthias Hamann, and Fabian Hundertmark. Canonical tree-decompositions of finite graphs I. Existence and algorithms. Journal of Combinatorial Theory, Series B, 116:1–24, 2016. doi:10.1016/j.jctb.2014.04.001.DOI
  23. [24]Johannes Carmesin, Reinhard Diestel, Matthias Hamann, and Fabian Hundertmark. Canonical tree-decompositions of finite graphs II. Essential parts. Journal of Combinatorial Theory, Series B, 118:268–283, 2016. doi:10.1016/j.jctb.2014.12.009.DOI
  24. [25]Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, and Maya Stein. Connectivity and tree structure in finite graphs. Combinatorica, 34:11–46, 2014. doi:10.1007/s00493-014-2898-5.DOI
  25. [26]William H. Cunningham and Jack Edmonds. A combinatorial decomposition theory. Canadian Journal of Mathematics, 32(3):734–765, 1980. doi:10.4153/CJM-1980-057-7.DOI
  26. [27]Johannes Carmesin and Sarah Frenkel. How to apply tree decomposition ideas in large networks?, 2023. arXiv:2312.12354.arxiv.org/abs/2312.12354
  27. [28]Johannes Carmesin and J. Pascal Gollin. Canonical tree-decompositions of a graph that display its k-blocks. Journal of Combinatorial Theory, Series B, 122:1–20, 2017. doi:10.1016/j.jctb.2016.05.001.DOI
  28. [29]ChatGPT. An eight-petal flower in a nuclear-pore contact graph, 2026. Computational research draft, 14 October 2026. Prepared in dialogue with Johannes Carmesin. URL: https://github.com/j-carmesin/j-carmesin.github.io/blob/main/npc_followup_paper.pdf.
  29. [30]Johannes Carmesin, Matthias Hamann, and Babak Miraf tab. Canonical trees of tree-decompositions. Journal of Combinatorial Theory, Series B, 152:1–26, 2022. doi:10.1016/j.jctb.2021.08.004.DOI
  30. [31]Johannes Carmesin and Jan Kurkofka. Entanglements. Journal of Combinatorial Theory, Series B, 164:17–28, 2024. doi:10.1016/j.jctb.2023.08.007.DOI
  31. [32]Johannes Carmesin and Jan Kurkofka. Canonical decompositions of 3-connected graphs. Advances in Combinatorics, 2025. Paper No. 7, 73 pp. doi:10.19086/aic.2025.7.DOI
  32. [33]Johannes Carmesin and Jan Kurkofka. Characterising 4-tangles through a connectivity property. The Electronic Journal of Combinatorics, 32(3):P3.26, 2025. doi:10.37236/12367.DOI
  33. [34]Marek Cygan, Paweł Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, and Magnus Wahlström. Randomized contractions meet lean decompositions. ACM Transactions on Algorithms, 17(1):6:1–6:30, 2021. doi:10.1145/3426738.DOI
  34. [35]Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Minimum bisection is fixed-parameter tractable. SIAM Journal on Computing, 48(2):417–450, 2019. doi:10.1137/140988553.DOI
  35. [37]Johannes Carmesin and M. S. Ramanujan. Augmenting to 4-vertex connectivity is fixed-parameter tractable. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2015–2042, 2026. doi:10.1137/1.9781611978971.73.
  36. [38]Ben Clark and Geoff Whittle. Tangles, trees, and flowers. Journal of Combinatorial Theory, Series B, 103(3):385–407, 2013. doi:10.1016/j.jctb.2013.03.002.DOI
  37. [39]Giuseppe Di Battista and Roberto Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15(4):302–318, 1996. doi:10.1007/BF01961541.DOI
  38. [40]Giuseppe Di Battista and Roberto Tamassia. On-line planarity testing. SIAM Journal on Computing, 25(5):956–997, 1996. doi:10.1137/S0097539794280736.DOI
  39. [41]Reinhard Diestel, Joshua Erde, and Daniel Weißauer. Structural submodularity and tangles in abstract separation systems. Journal of Combinatorial Theory, Series A, 167:155–180, 2019. doi:10.1016/j.jcta.2019.05.001.
  40. [42]Reinhard Diestel, Fabian Hundertmark, and Sahar Lemanczyk. Profiles of separations: In graphs, matroids, and beyond. Combinatorica, 39(1):37–75, 2019. doi:10.1007/s00493-017-3595-y.
  41. [43]Reinhard Diestel. Abstract separation systems. Order, 35(1):157–170, 2018. doi:10.1007/s11083-017-9424-5.DOI
  42. [44]Reinhard Diestel. Graph Theory. Springer, 6 edition, 2024. doi:10.1007/978-3-662-70107-2.DOI
  43. [46]Reinhard Diestel, Raphael W. Jacobs, Paul Knappe, and Jan Kurkofka. Canonical graph decompositions via coverings. to appear in Transactions of the American Mathematical Society, 2027. arXiv:2207.04855.
  44. [47]Michael Dinitz, Ama Koranteng, Guy Kortsarz, and Zeev Nutov. Improved approximations for relative survivable network design, 2023. A shorter version appeared in Approximation and Online Algorithms: 21st International Workshop, WAOA 2023, Lecture Notes in Computer Science, vol. 14297, pp. 190–204, Springer, 2023. https://doi.org/10.1007/978-3-031-49815-2_14. arXiv:2304.06656.
  45. [48]Efim A. Dinitz, Alexander V. Karzanov, and Mikhail V. Lomonosov. The structure of the system of all minimum edge cuts of a graph. Issledovaniya po Diskretnoi Optimizatsii, pages 290–306, 1976.
  46. [49]Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar graph isomorphism is in log-space. ACM Transactions on Computation Theory, 14(2), 2022. doi:10.1145/3543686.
  47. [52]Reinhard Diestel and Geoff Whittle. Tangles and the Mona Lisa, 2017. arXiv:1603.06652.arxiv.org/abs/1603.06652
  48. [62]Jim Geelen and Benson Joeris. A generalization of the grid theorem, 2016. arXiv:1609.09098.arxiv.org/abs/1609.09098
  49. [65]Martin Grohe. Tangled up in blue (a survey on connectivity, decompositions, and tangles), 2016. arXiv:1605.06704.
  50. [69]Zhongtian He, Shang-En Huang, and Thatchaphol Saranurak. Cactus representation of minimum cuts: Derandomize and speed up. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1503–1541, 2024. doi:10.1137/1.9781611977912.61.DOI
  51. [70]John E. Hopcroft and Robert E. Tarjan. A V² algorithm for determining isomorphism of planar graphs. Information Processing Letters, 1(1):32–34, 1971. doi:10.1016/0020-0190(71)90019-6.DOI
  52. [71]John E. Hopcroft and Robert E. Tarjan. Efficient planarity testing. Journal of the ACM, 21(4):549–568, 1974. doi:10.1145/321850.321852.DOI
  53. [72]John E. Hopcroft and J. K. Wong. Linear time algorithm for isomorphism of planar graphs (preliminary report). In Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC ’74, page 172–184, New York, NY, USA, 1974. doi:10.1145/800119.803896.DOI
  54. [73]Tanmay Inamdar, Daniel Loksh­tanov, Saket Saurabh, and Vaishali Surianarayanan. Parameterized complexity of fair bisection: (FPT-approximation meets unbreakability). In 31st Annual European Symposium on Algorithms (ESA 2023), volume 274 of Leibniz International Proceedings in Informatics (LIPIcs), pages 63:1–63:17, 2023. doi:10.4230/LIPIcs.ESA.2023.63.DOI
  55. [75]Raphael W. Jacobs and Paul Knappe. Canonical tree-decompositions of chordal graphs, 2025. arXiv:2512.18480.arxiv.org/abs/2512.18480
  56. [76]Raphael W. Jacobs, Paul Knappe, and Jan Kurkofka. Canonical graph decompositions via local separations, 2026. arXiv:2501.16170.arxiv.org/abs/2501.16170
  57. [77]Thor Johnson and Robin Thomas. Generating internally four-connected graphs. Journal of Combinatorial Theory, Series B, 85(1):21–58, 2002. doi:10.1006/jctb.2001.2089.DOI
  58. [78]Arkady Kanevsky. On the number of minimum size separating vertex sets in a graph and how to find all of them. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’90, page 411–421, USA, 1990. URL: https://dl.acm.org/doi/abs/10.5555/320176.320227.DOI
  59. [79]Solveig Klepper, Christian Elbracht, Diego Fioravanti, Jakob Kneip, Luca Rendsburg, Maximilian Teegen, and Ulrike von Luxburg. Clustering with tangles: Algorithmic framework and theoretical guarantees. Journal of Machine Learning Research, 24(190):1–56, 2023. URL: https://jmlr.org/papers/v24/21-1160.html.
  60. [80]Tomohiro Koana and Soh Kumabe. A single-exponential FPT algorithm for 2-vertex-connectivity augmentation, 2026. arXiv:2608.03830.arxiv.org/abs/2608.03830
  61. [81]Tuukka Korhonen. Linear-time algorithms for k-edge-connected components, k-lean tree decompositions, and more. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, pages 111–119, New York, NY, USA, 2025. doi:10.1145/3717823.3718123.DOI
  62. [83]Jan Kurkofka and Tim Planken. A characterisation of all vertex-transitive finite graphs of connectivity < 5, 2026. arXiv:2602.09811.arxiv.org/abs/2602.09811
  63. [84]Jan Kurkofka and Tim Planken. A Tutte-type canonical decomposition of 3- and 4-connected graphs. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2942–3021, 2026. doi:10.1137/1.9781611978971.110.DOI
  64. [85]Matthias Kriesell. Contractible non-edges in 3-connected graphs. Journal of Combinatorial Theory, Series B, 74(2):192–201, 1998. doi:10.1006/jctb.1998.1842.DOI
  65. [86]Matthias Kriesell. Contractible subgraphs in 3-connected graphs. Journal of Combinatorial Theory, Series B, 80(1):32–48, 2000. doi:10.1006/jctb.2000.1960.DOI
  66. [87]Matthias Kriesell. Almost all 3-connected graphs contain a contractible set of k vertices. Journal of Combinatorial Theory, Series B, 83(2):305–319, 2001. doi:10.1006/jctb.2001.2060.
  67. [88]Matthias Kriesell. A constructive characterization of 3-connected triangle-free graphs. Journal of Combinatorial Theory, Series B, 97(3):358–370, 2007. doi:10.1016/j.jctb.2006.06.002.
  68. [89]Matthias Kriesell. On the number of contractible triples in 3-connected graphs. Journal of Combinatorial Theory, Series B, 98(1):136–145, 2008. doi:10.1016/j.jctb.2007.05.003.
  69. [90]Matthias Kriesell. Vertex suppression in 3-connected graphs. Journal of Graph Theory, 57(1):41–54, 2008. doi:10.1002/jgt.20277.
  70. [91]Jon Kleinberg, Mark Sandler, and Aleksandrs Slivkins. Network failure detection and graph connectivity. SIAM Journal on Computing, 38(4):1330–1346, 2008. doi:10.1137/070697793.DOI
  71. [92]Ken-ichi Kawarabayashi and Mikkel Thorup. The minimum k-way cut of bounded size is fixed-parameter tractable. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 160–169, 2011. doi:10.1109/FOCS.2011.53.DOI
  72. [93]Tuukka Korhonen and Mikkel Thorup. Connectivity augmentation is fixed-parameter tractable, 2026. arXiv:2605.11757.arxiv.org/abs/2605.11757
  73. [98]Nicola Martinov. Uncontractable 4-connected graphs. Journal of Graph Theory, 6(3):343–344, 1982. doi:10.1002/jgt.3190060310.DOI
  74. [100]Petra Mutzel. The SPQR-tree data structure in graph drawing. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, volume 2719, pages 34–46, Berlin, Heidelberg, 2003. doi:10.1007/3-540-45061-0_4.DOI
  75. [101]Dániel Marx and László A. Végh. Fixed-parameter algorithms for minimum-cost edge-connectivity augmentation. ACM Transactions on Algorithms, 11(4), 2015. doi:10.1145/2700210.DOI
  76. [103]Zeev Nutov. On k-connectivity oracles in k-connected graphs, 2026. arXiv:2601.03643.arxiv.org/abs/2601.03643
  77. [104]Bogdan Oporowski, James Oxley, and Robin Thomas. Typical subgraphs of 3- and 4-connected graphs. Journal of Combinatorial Theory, Series B, 57(2):239–257, 1993. doi:10.1006/jctb.1993.1019.DOI
  78. [105]James Oxley, Charles Semple, and Geoff Whittle. The structure of the 3-separations of 3-connected matroids. Journal of Combinatorial Theory, Series B, 92(2):257–293, 2004. Special Issue Dedicated to Professor W.T. Tutte. doi:10.1016/j.jctb.2004.03.006.DOI
  79. [106]Seth Pettie. A cactus-type structure for vertex connectivity? Talk abstract in Data Structures for the Cloud and External Memory Data (Dagstuhl Seminar 19051), Dagstuhl Reports, 9(1):118, 2019. Section 3.21. doi:10.4230/DagRep.9.1.104.
  80. [107]Tim Planken. Cops and invisible robbers in k-connected graphs of treewidth k. In preparation.
  81. [109]Stefan Petrovic, Dipanjan Samanta, Thibaud Perriches, Christopher J. Bley, Karsten Thierbach, Bonnie Brown, Si Nie, George W. Mobbs, Taylor A. Stevens, Xiaoyu Liu, Giovani Pinton Tomaleri, Lucas Schaus, and André Hoelz. Architecture of the linker-scaffold in the nuclear pore. Science, 376(6598):eabm9798, 2022. doi:10.1126/science.abm9798.DOI
  82. [112]Seth Pettie and Longhui Yin. The structure of minimum vertex cuts. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 105:1–105:20, Dagstuhl, Germany, 2021. doi:10.4230/LIPIcs.ICALP.2021.105.DOI
  83. [113]Chengfu Qin and Guoli Ding. A chain theorem for 4-connected graphs. Journal of Combinatorial Theory, Series B, 134:341–349, 2019. doi:10.1016/j.jctb.2018.07.005.DOI
  84. [115]Neil Robertson and Paul D. Seymour. Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2):153–190, 1991. doi:10.1016/0095-8956(91)90061-N.
  85. [116]Neil Robertson and Paul D. Seymour. Graph minors. XXIII. Nash-Williams’ immersion conjecture. Journal of Combinatorial Theory, Series B, 100(2):181–205, 2010. doi:10.1016/j.jctb.2009.07.003.DOI
  86. [117]Akira Saito. Splitting and contractible edges in 4-connected graphs. Journal of Combinatorial Theory, Series B, 88(2):227–235, 2003. doi:10.1016/S0095-8956(02)00043-6.DOI
  87. [118]Paul D. Seymour. Decomposition of regular matroids. Journal of Combinatorial Theory, Series B, 28(3):305–359, 1980. doi:10.1016/0095-8956(80)90075-1.DOI
  88. [119]Peter J. Slater. A classification of 4-connected graphs. Journal of Combinatorial Theory, Series B, 17(3):281–298, 1974. doi:10.1016/0095-8956(74)90034-3.DOI
  89. [121]Paul D. Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B, 58(1):22–33, 1993. doi:10.1006/jctb.1993.1027.DOI
  90. [124]Vera Traub and Rico Zenklusen. A (1.5 + ε)-approximation algorithm for weighted connectivity augmentation. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC ’23, page 1820–1833, 2023. doi:10.1145/3564246.3585122.DOI

Paper details

vlnc:W_qjtfwt5q
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents