An exponential lower bound for cut sparsifiers in planar graphs

DOI10.4230/LIPICS.IPEC.2017.24MaRDI QIDQ5111883zbMATH OpenFDO

Authors Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz

Publication date 27 May 2020

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

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)

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

Cites work

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

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)