We present results related to satisfying shortest path queries on a planar graph stored in external memory. In particular, we show how to store rooted trees in external memory so that bottom-up paths can be traversed I/O-efficiently, and we present I/O-efficient algorithms for triangulating planar graphs and computing small separators of such graphs. Using these techniques, we can construct a data structure that allows for answering shortest path queries on a planar graph I/O-efficiently.

Additional Metadata
Persistent URL dx.doi.org/10.1007/3-540-48686-0_5
Citation
Hutchinson, D. (David), Maheshwari, A, & Zeh, N. (Norbert). (1999). An external memory data structure for shortest path queries. doi:10.1007/3-540-48686-0_5