Implementing the Topological Model Succinctly

José Fuentes, Gonzalo Navarro, and Diego Seco

We show that the topological model, a semantically rich standard to represent GIS data, can be encoded succinctly while efficiently answering a number of topology-related queries. We build on recent succinct planar graph representations so as to encode a model with m edges within 4m+o(m) bits and answer various queries relating nodes, edges, and faces in o(log log m) time, or any time in omega(log m) for a few complex ones.