Name
Abstract | ||
|---|---|---|
Abstract 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00453-015-0086-7 | Algorithmica |
Keywords | Field | DocType |
External memory algorithms,Path traversal,Planar graphs,Succinct data structures | Block size,Discrete mathematics,Combinatorics,Tree traversal,Vertex (geometry),Succinct data structure,Input/output,Connected component,Triangulated irregular network,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
77 | 3 | 1432-0541 |
Citations | PageRank | References |
0 | 0.34 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Craig Dillabaugh | 1 | 12 | 4.25 |
| Meng He | 2 | 308 | 22.04 |
| Anil Maheshwari | 3 | 869 | 104.47 |
| Norbert Zeh | 4 | 55 | 6.97 |