An external memory data structure for shortest path queries
We present results related to satisfying shortest path queries on a planar graph stored in external memory. Let N denote the number of vertices in the graph and sort(N) denote the number of input/output (I/O) operations required to sort an array of length N: (1) We describe a blocking for rooted trees to support bottom-up traversals of these trees in O(K/B) I/Os, where K is the length of the traversed path. The space required to store the tree is O(N/B) blocks, where N is the number of vertices of the tree and B is the block size. (2) We give an algorithm for computing a 2/3-separator of size O(N) for a given embedded planar graph. Our algorithm takes O(sort(N)) I/Os, provided that a breadth-first spanning tree is given. (3) We give an algorithm for triangulating embedded planar graphs in O(sort(N)) I/Os. We use these results to construct a data structure for answering shortest path queries on planar graphs. The data structure uses O(N 3/2/B) blocks of external memory and allows for a shortest path query to be answered in O((N+K)/DB) I/Os, where K is the number of vertices on the reported path and D is the number of parallel disks.
|Keywords||External-memory algorithms, Graph algorithms, Planar graphs, Shortest paths|
|Journal||Discrete Applied Mathematics|
Hutchinson, D. (David), Maheshwari, A, & Zeh, N. (Norbert). (2003). An external memory data structure for shortest path queries. In Discrete Applied Mathematics (Vol. 126, pp. 55–82). doi:10.1016/S0166-218X(02)00217-2