View publication
| Title | Navigating Planar Topologies in Near-Optimal Space and Time |
| Authors | José Fuentes-Sepúlveda, Gonzalo Navarro, Diego Seco |
| Publication date | 2023 |
| Abstract |
We show that any embedding of a planar graph can be encoded succinctly while efficiently answering a number of topological queries near-optimally. More precisely, we build on a succinct representation that encodes an embedding of m edges within 4m bits, which is close to the information-theoretic lower bound of about 3.58m. With 4m + o(m) bits of space, we show how to answer a number of topological queries relating nodes, edges, and faces, most of them in any time in omega(1). Indeed, 3.58m + o(m) bits suffice if the graph has no self-loops and no nodes of degree one. Further, we show that with O(m) bits of space we can solve all those operations in O(1) time. |
| Pages | article 101922 |
| Volume | 109 |
| Journal name | Computational Geometry Theory and Applications |
| Publisher | Elsevier Science (Amsterdam, The Netherlands) |
| Reference URL |
|