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.
|Keywords||External memory algorithms, Path traversal, Planar graphs, Succinct data structures|
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