Improved Guarantees for Vertex Sparsification in Planar Graphs
From MaRDI portal
Publication:5208743
DOI10.1137/17M1163153zbMath1431.05047arXiv1702.01136WikidataQ126385123 ScholiaQ126385123MaRDI QIDQ5208743
Pan Peng, Gramoz Goranci, Monika R. Henzinger
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.01136
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A node-capacitated Okamura-Seymour theorem
- Circular planar graphs and resistor networks
- Multicommodity flows in planar graphs
- An existence theory for pairwise balanced designs. III: Proof of the existence conjectures
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- On the distortion required for embedding finite metric spaces into normed spaces
- A characterization of the components of the graphs \(D(k,q)\)
- 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
- Sparse Sourcewise and Pairwise Distance Preservers
- Dynamic Plane Transitive Closure
- Approximate distance oracles
- A Tight Lower Bound for the Steiner Point Removal Problem on Trees
- Complexity of network synchronization
- Universality considerations in VLSI circuits
- Delta-Wye Transformations and the Efficient Reduction of Two-Terminal Planar Graphs
- A new series of dense graphs of high girth
- A Hierarchy of Lower Bounds for Sublinear Additive Spanners
- Linear Size Distance Preservers
- Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
- Steiner Point Removal --- Distant Terminals Don't (Really) Bother
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Distance-Preserving Subgraphs of Interval Graphs
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion
- Refined Vertex Sparsifiers of Planar Graphs
- Distance-Preserving Graph Contractions
- The 4/3 additive spanner exponent is tight
- Towards (1 + ∊)-Approximate Flow Sparsifiers
- On vertex sparsifiers with Steiner nodes
- Routing in undirected graphs with constant congestion
- Compact oracles for reachability and approximate distances in planar digraphs
- Embedding k-Outerplanar Graphs into l1
- Cutting Corners Cheaply, or How to Remove Steiner Points
- The Transitive Reduction of a Directed Graph
- Depth-First Search and Linear Graph Algorithms
- Mimicking Networks and Succinct Representations of Terminal Cuts
- Vertex Sparsifiers: New Results from Old Techniques
This page was built for publication: Improved Guarantees for Vertex Sparsification in Planar Graphs