Source-linked AI summary
Deterministic Incremental Triconnectivity in $O(\log^2 n)$ Worst-Case Time
Niels Inselmann Christiansen, Eva Rotenberg
TL;DR
The paper addresses maintaining pairwise triconnectivity as graphs grow through incremental updates. It maintains an SPQR-tree representation for biconnected graphs, obtaining deterministic worst-case O(log n) operations and queries there; combined with Holm and Rotenberg [HR20], the general-graph bound improves from O(log^3 n) to O(log^2 n).
Problem
The paper addresses maintaining pairwise triconnectivity during incremental updates, including edge insertions and subdivisions, with queries about whether two vertices have three internally vertex-disjoint paths.
Source: §1 · p. 2Method
For biconnected graphs, the data structure maintains an SPQR-tree representation ready for edge insertion with only a logarithmic number of tree changes.
Source: §5 · p. 25Results
O(log^3 n) to O(log^2 n): the general-graph worst-case bound for incremental triconnectivity improves by a factor of O(log n).
Source: §5 · p. 25Takeaways & Limitations
For biconnected graphs, the result comes within an O(log log n) factor of the cell-probe incremental-connectivity lower bound.
Source: §5 · p. 25In the fully dynamic setting, no data structure is known with polylogarithmic update and query times for triconnectivity queries between vertex pairs.
Source: §5 · p. 25
Abstract
from arXiv · showhide
We consider the problem of maintaining the triconnectivity in some biconnected graph G in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries of the form "are there at least three vertex disjoint paths between a and b?". All algorithms presented in this paper are deterministic. All queries and updates are answered in worst-case $O(\log n)$ time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get an algorithm for general graphs with a worst-case running time of $O(\log^2 n)$ per operation. These algorithms represent an improvement of the state-of-the-art by a factor of $O(\log n)$.
1 Introduction & preliminaries
The paper tackles incremental triconnectivity maintenance and gives deterministic worst-case bounds for biconnected and general graphs. It develops this result through SPQR-tree maintenance and establishes the graph and separator terminology used in the paper.
1 Introduction & preliminaries
- Incremental triconnectivity matters for planar graph drawing because triconnected graphs have unique planar embeddings, and their components inform embeddings of planar graphs.The static triconnected-component algorithm of Hopcroft and Tarjan runs in linear time.Source: §1 · p. 2
1.1 Related Work
- Earlier work gave O(log^3 n) worst-case incremental triconnectivity for general graphs [HR20], while this paper reports deterministic worst-case guarantees and pair-wise relational queries.Incremental biconnectivity had an O(log n) bound; the paper contrasts its guarantees with recent randomized, amortized general vertex-connectivity algorithms [Ade+26].Source: §1.1 · pp. 2–3
1.2 Our contribution
- Biconnected graphs admit deterministic worst-case O(log n) update and triconnectivity-query times; the general-graph bound is O(log^2 n).The biconnected structure supports InsertVertex and InsertEdge, while the general-graph result follows by combining it with Holm and Rotenberg [HR20].Source: §1.2 · p. 3
1.3 Techniques and challenges
- The approach stores the triconnected components in an SPQR-tree and avoids an extra O(log n) search factor by storing information in the ST-tree.This targets the search for a specific edge needed during SPQR-tree insertion.Source: §1.3 · p. 3
1.4 Preliminaries
- A graph is triconnected when every vertex pair has three internally vertex-disjoint paths; a 2-separator is also called a split pair.A k-separator is a k-cut, and Menger’s theorem relates k-connectivity to the absence of vertex sets of size k−1 that disconnect the graph [Men27].Source: §1.4 · p. 4
2 Heavy Path Decompositions
The section develops weighted heavy path decompositions and a dynamic-tree representation that supports their updates in logarithmic worst-case time. These operations provide the tree machinery used later to maintain triconnected components.
2 Heavy Path Decompositions
- A u-exposed decomposition makes the u-to-root path solid, while each node has at most one solid child.Solid edges otherwise follow the heavy-edge decomposition.Source: §2 · p. 5
- Expose uses one splice per light-depth step, while conceal uses at most one more slice than the light depth.Splice and slice locally change edge colors; expose and conceal apply them along the root path.Source: §2 · p. 6
2.1 Implementing Heavy Path Decompositions
- Biased search trees represent heavy paths and child sets, yielding a logarithmic number of search-tree operations for heavy path operations.Parent pointers and repeated Path and Tail calls traverse a node-to-root path.Source: §2.1 · pp. 6–7
- Expose, conceal, reverse, link-exposed, and cut-exposed take O(log(W/w_t(v))) time in a weighted heavy path decomposition.The structure maintains a directed tree and supports all five operations in this bound.Source: §2.1 · p. 10
3 Incremental Triconnectivity for Biconnected Graphs
The section maintains a representation of a biconnected graph’s triconnected components using an SPQR-tree. It defines a critical path to support triconnectivity queries and incremental updates by edge insertion and subdivision.
3 Incremental Triconnectivity for Biconnected Graphs
- Edge insertion and subdivision span the biconnected graphs incrementally, while the SPQR-tree represents their triconnected components.The SPQR-tree is unique, and its node skeletons are the graph’s triconnected components.Source: §3 · p. 10, §3.1 · p. 11
3.1 SPQR-trees
- SPQR-tree nodes have S, P, or R labels and associated skeletons; adjacent skeletons share a separation pair represented by virtual edges.S skeletons are cycles, P skeletons are parallel edges on two vertices, and the tree is unique.Source: §3.1 · pp. 10–11
- The critical path m(x, y) is the unique SPQR-tree region determined by which nodes contain x and y.It is a single node, an adjacent pair, a shared P-node, or the path between their containing nodes.Source: §3.1 · pp. 11–12
3.2 Answering queries
- A pair of vertices are triconnected if and only if they share a P- or R-node in the SPQR-tree.If they share only one S-node, the cycle structure implies a neighboring P-node must also contain them.Source: §3.2 · p. 12
3.3 Updates
- The update primitives merge adjacent same-type nodes by combining their skeletons and split S-nodes into two new S-nodes along disjoint paths.Subdivision adds a vertex by applying cases based on the critical path; an existing edge makes one case irrelevant.Source: §3.3 · pp. 13–14
- For edge insertion, the critical path is contracted into an R-node when the endpoints are linked; pairs in its P- and R-nodes become triconnected.Vertices outside those nodes retain their connective properties; insertion cases also split S-nodes and create or connect P-nodes.Source: §3.3 · p. 13
4 SPQR-trees as heavy path decompositions
The section represents SPQR-trees with heavy paths and path summaries to support edge insertions and graph operations through a constant number of heavy-path operations, avoiding traversal of m(u, v). It gives deterministic worst-case bounds of O(log n) for biconnected graphs and O(log² n) for general graphs, using linear space.
4.1 Splitting along heavy paths
- Split separates proper child groups into at most two secondary children, and merge contracts those children back into their parent.Moved virtual edges carry their corresponding tree edges; new children connect by dashed edges, with a heavy-child connection made solid.Source: §4.1 · p. 15
- Splits and merges preserve the relaxed-tree invariants; pre-splitting restricts splittable primary nodes to children of R-nodes, with at most two repairs after select or deselect.The invariants also ensure that no node is both splittable and mergeable; any relaxed tree satisfying the earlier invariants can be obtained from a strict SPQR-tree by splitting selected nodes.Source: §4.1 · pp. 15–17
4.2 Maintaining a Pre-Split SPQR-tree Under Heavy Path Operations
- Splice and slice preserve the pre-split invariants and take O(log W / w(μ′)) time, while expose and conceal retain their logarithmic weight-based bound.The stated splice and slice bound assumes split and merge take worst-case O(1).Source: §4.2 · pp. 17–18
- Contracting the root heavy path into one R-node takes O(1) and preserves the pre-split invariants.The representation implements contraction by incrementing the value of every edge on that path.Source: §4.2 · pp. 18–19
4.3 Representing the Pre-split SPQR-tree
- P-node dashed children use a weight-ordered biased search tree, while S-node children use two biased search trees that preserve their cyclic order.The S-node trees are split and concatenated as the node’s solid child changes.Source: §4.3 · p. 19
- R-nodes are represented by networks of obsolete nodes of degree at most 4, with consistent vertex representatives and poles guiding edge placement.No SPQR-tree operation subdivides a positive edge, so once both poles lie in one R-node they remain there.Source: §4.3 · p. 20
4.4 Finding critical paths
- Heavy-path summaries and pole properties let the structure locate critical paths, including relevant off-path edges, from vertex representatives.The method augments biased-search-tree nodes with marked-path summaries and applies them to heavy paths to find critical-path endpoints.Source: §4.4 · pp. 21–22
4.5 Implementing SPQR-tree operation
- Triconnected queries, subdivisions, and edge insertions are implemented using a constant number of heavy-path operations.A query checks the critical-path length and whether an endpoint is a P- or R-node; insertion handles cases based on the critical path's form.Source: §4.5 · pp. 23–24
- Theorem 1 gives a linear-space data structure for biconnected graphs with deterministic worst-case O(log n) InsertVertex and InsertEdge operations and Triconnected queries.Source: §4.5 · p. 24
- Corollary 2 extends the bounds to general graphs: linear space and deterministic worst-case O(log^2 n) for InsertVertex, InsertEdge, and Triconnected.Source: §4.5 · p. 25
5 Conclusion and Open Problems
The paper maintains triconnectivity in biconnected graphs with logarithmic-time updates and queries, and combines this result with prior work to obtain a logarithmic-squared bound for general graphs. It also identifies open questions about matching a lower bound, improving general-graph performance, and fully dynamic triconnectivity.
5 Conclusion and Open Problems
- For biconnected graphs, the SPQR-tree representation supports triconnectivity queries, edge insertions, and subdivisions in worst-case O(log n) time.The representation stays ready for an edge insertion with only a logarithmic number of tree changes.Source: §5 · p. 25
- For general graphs, combining the result with Holm and Rotenberg [HR20] gives worst-case O(log^2 n) time per query and operation, improving the previous O(log^3 n) upper bound.Source: §5 · p. 25
- The biconnected-graph result is within an O(log log n) factor of the cell-probe incremental-connectivity lower bound, and matching that bound remains open.Source: §5 · p. 25
- Open problems include an O(log n) upper bound for general-graph triconnectivity and polylogarithmic update and query times for fully dynamic triconnectivity.Source: §5 · p. 25
6 Declaration of AI Usage
The authors report that they wrote the ideas, proofs, and text without AI; Claude Opus 5.5 was used for minor editing and phrasing.
6 Declaration of AI Usage
- The authors state that the ideas, proofs, and text were written without AI.Source: §6 · p. 25
- Claude Opus 5.5 was used for minor editing and phrasing tasks.Source: §6 · p. 25