Decremental SPQR-trees for Planar Graphs
From MaRDI portal
Publication:5009609
DOI10.4230/LIPIcs.ESA.2018.46OpenAlexW2809834283MaRDI QIDQ5009609
Jacob Holm, Adam Karczmarz, Giuseppe F. Italiano, Jakub Łącki, Eva Rotenberg
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1806.10772
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The construction and classification of self-dual spherical polyhedra
- Mantaining dynamic matrices for fully dynamic transitive closure
- Efficient Union-Find for planar graphs and other sparse graph classes
- Dynamic planar embeddings of dynamic graphs
- On-line maintenance of triconnected components with SPQR-trees
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Decremental 2- and 3-connectivity on planar graphs
- A V log V algorithm for isomorphism of triconnected planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Generation of simple quadrangulations of the sphere
- Improved Deterministic Algorithms for Decremental Reachability and Strongly Connected Components
- The Power of Dynamic Distance Oracles
- Optimal Decremental Connectivity in Planar Graphs.
- Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time
- Near-optimal fully-dynamic graph connectivity
- Faster Fully-Dynamic Minimum Spanning Forest
- Dynamic Plane Transitive Closure
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Worst-case update times for fully-dynamic all-pairs shortest paths
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Separator-Based Sparsification II: Edge and Vertex Connectivity
- Sampling to provide or to bound: With applications to fully dynamic graph algorithms
- Sparsification—a technique for speeding up dynamic graph algorithms
- Faster worst case deterministic dynamic connectivity
- Representations of Planar Graphs
- On-Line Planarity Testing
- Dividing a Graph into Triconnected Components
- Decremental single-source reachability in planar digraphs
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
- Fully-dynamic minimum spanning forest with improved worst-case update time
- Contracting a Planar Graph Efficiently
- Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time
- Fully Dynamic Maximal Matching in $O(\log n)$ Update Time
- TESTING MUTUAL DUALITY OF PLANAR GRAPHS
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Improved algorithms for min cut and max flow in undirected planar graphs
- A new approach to dynamic all pairs shortest paths
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster Deterministic Fully-Dynamic Graph Connectivity
This page was built for publication: Decremental SPQR-trees for Planar Graphs
