I/O and Space-Efficient Path Traversal in Planar Graphs

摘要

We present a technique for representing bounded-degree planar graphs succinctly while permitting I/O-efficient path traversal. To represent a graph G on N vertices, each with an associated key of q = O(lg N) bits, we use N q + O(N) + o(N q) bits. Using this representation, a path of length K can be traversed with O(K/ lg B) I/Os, where B is the disk block size. Our structure may be adapted to represent, with similar space bounds, a terrain modeled as a triangular-irregular network to support traversal of a path that visits K triangles using O(K/ lg B) I/Os. This structure can be used to answer a number of useful queries efficiently, such as reporting terrain profiles, trickle paths and connected components.