An exponential lower bound for cut sparsifiers in planar graphs

DOI10.4230/LIPICS.IPEC.2017.24zbMATH Open1443.68134arXiv1706.06086MaRDI QIDQ5111883FDOQ5111883

Authors: Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz 

Publication date: 27 May 2020

Full work available at URL: https://arxiv.org/abs/1706.06086

Recommendations

• An exponential lower bound for cut sparsifiers in planar graphs
• Mimicking Networks and Succinct Representations of Terminal Cuts
• Refined vertex sparsifiers of planar graphs
• All-Pairs Min-Cut in Sparse Networks
• On mimicking networks representing minimum terminal cuts

zbMATH Keywords

planar graphsmimicking networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Representative sets and irrelevant vertices: new tools for kernelization
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Vertex Sparsifiers: New Results from Old Techniques
• Metric extension operators, vertex sparsifiers and Lipschitz extendability
• On mimicking networks representing minimum terminal cuts
• Flows in one-crossing-minor-free graphs
• Improved guarantees for vertex sparsification in planar graphs
• On vertex sparsifiers with Steiner nodes
• Mimicking Networks and Succinct Representations of Terminal Cuts

Cited In (3)

• An exponential lower bound for cut sparsifiers in planar graphs
• On mimicking networks representing minimum terminal cuts
• Refined vertex sparsifiers of planar graphs

This page was built for publication: An exponential lower bound for cut sparsifiers in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111883)