An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications Vol. 22, no. 2, pp. 297-327, 2018. Regular paper. Abstract A vertex separator, in general, refers to a set of vertices whose removal disconnects the original graph into subgraphs possessing certain nice properties. Such separators have proved useful for solving a variety of graph problems. The core contribution of the paper is an I/O-efficient algorithm that finds, on any $d$-dimensional grid graph, a small vertex separator which mimics the well-known separator of [Maheshwari and Zeh, SICOMP'08] for planar graphs. We accompany our algorithm with two applications. First, by integrating our separators with existing algorithms, we strengthen the current state-of-the-art results of three fundamental problems on 2D grid graphs: finding connected components, finding single source shortest paths, and breadth-first search. Second, we show how our separator-algorithm can be deployed to perform density-based clustering on $d$-dimensional points I/O-efficiently. Submitted: May 2017. Reviewed: January 2018. Revised: February 2018. Accepted: June 2018. Final: July 2018. Published: August 2018. Communicated by Paolo Ferragina article (PDF) BibTeX