Refined Vertex Sparsifiers of Planar Graphs
From MaRDI portal
Publication:5208742
DOI10.1137/17M1151225zbMath1439.68017arXiv1702.05951WikidataQ126402357 ScholiaQ126402357MaRDI QIDQ5208742
Havana Rika, Robert Krauthgamer
Publication date: 10 January 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.05951
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Reachability Preservers: New Extremal Bounds and Approximation Algorithms ⋮ Steiner Point Removal with Distortion $O(\log {k})$ using the Relaxed-Voronoi Algorithm ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ An exponential lower bound for cut sparsifiers in planar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple algorithm for multicuts in planar graphs with outer terminals
- Multicommodity flows in planar graphs
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Efficient algorithms for \(k\)-terminal cuts on planar graphs
- Flow-cut gaps for integer and fractional multiflows
- Computing mimicking networks
- An exponential lower bound for cut sparsifiers in planar graphs
- On mimicking networks representing minimum terminal cuts
- Metric extension operators, vertex sparsifiers and Lipschitz extendability
- Preserving Terminal Distances Using Minors
- Extensions and limits to vertex sparsification
- Vertex Sparsification in Trees
- Spectral Sparsification of Graphs
- Shortest path queries in planar graphs
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
- On the Complexity of Covering Vertices by Faces in a Planar Graph
- Planar graph decomposition and all pairs shortest paths
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Steiner Point Removal --- Distant Terminals Don't (Really) Bother
- An Optimal Synchronizer for the Hypercube
- A face cover perspective to ℓ1 embeddings of planar graphs
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- On the geometry of graphs with a forbidden minor
- Flow-Cut Gaps and Face Covers in Planar Graphs
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- Towards (1 + ∊)-Approximate Flow Sparsifiers
- On vertex sparsifiers with Steiner nodes
- Cutting Corners Cheaply, or How to Remove Steiner Points
- Mimicking Networks and Succinct Representations of Terminal Cuts
- Vertex Sparsifiers: New Results from Old Techniques
