I/O-Efficient Path Traversal in Succinct Planar Graphs
详细信息 查看全文
- 作者：Craig Dillabaugh ; Meng He ; Anil Maheshwari ; Norbert Zeh
- 关键词：External memory algorithms ; Path traversal ; Planar graphs ; Succinct data structures
- 刊名：Algorithmica
- 出版年：2017
- 出版时间：March 2017
- 年：2017
- 卷：77
- 期：3
- 页码：714-755
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Algorithm Analysis and Problem Complexity; Theory of Computation; Mathematics of Computing; Algorithms; Computer Systems Organization and Communication Networks; Data Structures, Cryptology and Inform
- 出版者：Springer US
- ISSN：1432-0541
- 卷排序：77
文摘
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 \(\lg {N}\) denotes \(\log _2{N}\)) each with an associated key of \(q= \mathrm {O}\left( \lg N\right) \) bits, can be stored in \(Nq+ \mathrm {O}\left( N\right) + \mathrm {o}\left( Nq\right) \) bits and traversing a path of length K takes \(\mathrm {O}\left( K / \lg B\right) \) 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 \(\mathrm {O}\left( K / \lg B\right) \) 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.