Improved guarantees for vertex sparsification in planar graphs
From MaRDI portal
Publication:5111733
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Graph minors (05C83) Metric embeddings as related to computational problems and algorithms (68R12)
Recommendations
Cites work
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Approximate distance oracles
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Circular planar graphs and resistor networks
- Compact oracles for reachability and approximate distances in planar digraphs
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
- Dynamic Plane Transitive Closure
- Edge-disjoint paths in planar graphs with constant congestion
- Embedding k-Outerplanar Graphs into l1
- Extensions and limits to vertex sparsification
- Flow-cut gaps for integer and fractional multiflows
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Linear size distance preservers
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Mimicking Networks and Succinct Representations of Terminal Cuts
- Multicommodity flows in planar graphs
- On mimicking networks representing minimum terminal cuts
- On the distortion required for embedding finite metric spaces into normed spaces
- On vertex sparsifiers with Steiner nodes
- Refined vertex sparsifiers of planar graphs
- Routing in undirected graphs with constant congestion
- Sparse Sourcewise and Pairwise Distance Preservers
- Spectral sparsification of graphs
- Steiner points in tree metrics don't (really) help
- Terminal embeddings
- The Transitive Reduction of a Directed Graph
- Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
- Universality considerations in VLSI circuits
- Vertex sparsification in trees
- Vertex sparsifiers: new results from old techniques
Cited in
(9)- An exponential lower bound for cut sparsifiers in planar graphs
- Improved guarantees for vertex sparsification in planar graphs
- Near-optimal distance emulator for planar graphs
- The power of vertex sparsifiers in dynamic graph algorithms
- Vertex Sparsifiers: New Results from Old Techniques
- Vertex sparsifiers: new results from old techniques
- An exponential lower bound for cut sparsifiers in planar graphs
- Steiner point removal with distortion \(O(\log k)\) using the \texttt{Relaxed-Voronoi} algorithm
- Refined vertex sparsifiers of planar graphs
This page was built for publication: Improved guarantees for vertex sparsification in planar graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111733)
