I/O-Efficient Planar Separators

DOI10.1137/S0097539705446925zbMath1163.05053OpenAlexW1972414329MaRDI QIDQ3631891

Anil Maheshwari, Norbert Zeh

Publication date: 22 June 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

planar graphsgraph algorithmsgraph separatorsmemory hierarchiesI/O-efficient algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory (05C90) Large-scale problems in mathematical programming (90C06) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications ⋮ Building an optimal point-location structure in \(O(\operatorname{sort}(n))\) I/Os ⋮ Via Detours to I/O-Efficient Shortest Paths

This page was built for publication: I/O-Efficient Planar Separators