Multiway simple cycle separators and I/O-efficient algorithms for planar graphs

DOI10.1137/1.9781611973105.65MaRDI QIDQ5741773zbMATH OpenOpenAlexFDO

Authors Lars Arge, Freek Van Walderveen, Norbert Zeh

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973105.65

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• I/O-Efficient Planar Separators
• scientific article; zbMATH DE number 2119685
• Algorithm Theory - SWAT 2004
• On external-memory MST, SSSP and multi-way planar graph separation
• On External-Memory Planar Depth First Search

Cited in

(16)

• Optimal decremental connectivity in planar graphs
• Faster shortest paths in dense distance graphs, with applications
• Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os
• scientific article; zbMATH DE number 1617278 (Why is no real title available?)
• On external-memory MST, SSSP and multi-way planar graph separation
• I/O-Efficient Planar Separators
• An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
• I/O-Optimal Algorithms for Outerplanar Graphs
• scientific article; zbMATH DE number 2119685 (Why is no real title available?)
• Contracting a planar graph efficiently
• Short and simple cycle separators in planar graphs
• Algorithm Theory - SWAT 2004
• An efficient oracle for counting shortest paths in planar graphs
• An efficient oracle for counting shortest paths in planar graphs
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Good r-divisions imply optimal amortized decremental biconnectivity

This page was built for publication: Multiway simple cycle separators and I/O-efficient algorithms for planar graphs

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