I/O-Efficient Path Traversal in Succinct Planar Graphs

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