Improved Guarantees for Vertex Sparsification in Planar Graphs

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

zbMATH Keywords

planar graphscut sparsifiersvertex sparsificationreachability-preserving minor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Reachability Preservers: New Extremal Bounds and Approximation Algorithms

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