Improved guarantees for vertex sparsification in planar graphs
DOI10.4230/LIPICS.ESA.2017.44zbMATH Open1442.68171MaRDI QIDQ5111733FDOQ5111733
Authors: Gramoz Goranci, Pan Peng, Monika R. Henzinger 
Publication date: 27 May 2020
Recommendations
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)
Cites Work
- Spectral sparsification of graphs
- Approximate distance oracles
- The Transitive Reduction of a Directed Graph
- Circular planar graphs and resistor networks
- Sparse Sourcewise and Pairwise Distance Preservers
- Universality considerations in VLSI circuits
- Compact oracles for reachability and approximate distances in planar digraphs
- Title not available (Why is that?)
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Multicommodity flows in planar graphs
- Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
- Embedding k-Outerplanar Graphs into l1
- Edge-disjoint paths in planar graphs with constant congestion
- On the distortion required for embedding finite metric spaces into normed spaces
- Steiner points in tree metrics don't (really) help
- A node-capacitated Okamura-Seymour theorem
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Vertex sparsifiers: new results from old techniques
- Routing in undirected graphs with constant congestion
- Title not available (Why is that?)
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Linear Size Distance Preservers
- Dynamic Plane Transitive Closure
- On mimicking networks representing minimum terminal cuts
- Refined Vertex Sparsifiers of Planar Graphs
- Towards (1 + ∊)-Approximate Flow Sparsifiers
- On vertex sparsifiers with Steiner nodes
- Mimicking Networks and Succinct Representations of Terminal Cuts
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Vertex Sparsification in Trees
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Title not available (Why is that?)
- Extensions and limits to vertex sparsification
- Preserving Terminal Distances Using Minors
Cited In (7)
- An exponential lower bound for cut sparsifiers in planar graphs
- Title not available (Why is that?)
- Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm
- Vertex Sparsifiers: New Results from Old Techniques
- Refined Vertex Sparsifiers of Planar Graphs
- Improved Guarantees for Vertex Sparsification in Planar Graphs
- Title not available (Why is that?)
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)
