We present a technique for representing bounded-degree planar graphs in a succinct fashion while permitting I/O-efficient traversal of paths. Using our representation, a graph with N vertices, (In this paper (Formula presented.) denotes (Formula presented.)) each with an associated key of (Formula presented.) bits, can be stored in (Formula presented.) bits and traversing a path of length K takes (Formula presented.) I/Os, where B denotes the disk block size. By applying our construction to the dual of a terrain represented as a triangular irregular network, we can represent the terrain in the above space bounds and support path traversals on the terrain using (Formula presented.) I/Os, where K is the number of triangles visited by the path. This is useful for answering a number of queries on the terrain, such as reporting terrain profiles, trickle paths, and connected components.

Additional Metadata
Keywords External memory algorithms, Path traversal, Planar graphs, Succinct data structures
Persistent URL dx.doi.org/10.1007/s00453-015-0086-7
Journal Algorithmica
Citation
Dillabaugh, C. (Craig), He, M. (Meng), Maheshwari, A, & Zeh, N. (Norbert). (2017). I/O-Efficient Path Traversal in Succinct Planar Graphs. Algorithmica, 77(3), 714–755. doi:10.1007/s00453-015-0086-7