Fuentes Sepúlveda, JoséGatica, DiegoNavarro, GonzaloRodríguez, M. AndreaSeco, Diego2024-07-092023-06J. Fuentes-Sepúlveda, D. Gatica, G. Navarro, M. A. Rodríguez, and D. Seco, "Compact representations of spatial hierarchical structures with support for topological queries", Information and Computation, Vol. 292, article 105029, Jun. 2023, doi: 10.1016/j.ic.2023.1050290890-5401http://hdl.handle.net/2183/37816©2023 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/byncnd/ 4.0/. This version of the article has been accepted for publication in Future Generation Computer Systems. The Version of Record is available online at https:// doi.org/10.1016/j.ic.2023.105029[Abstract]: Among different spatial data models, the topological model for spatial regions explicitly represents common boundaries. This model pursues the efficiency of topology-related queries and the elimination of data redundancy. This paper proposes several space-efficient data structures to support access to the topological representation of two-dimensional regions that are organized in a multi-granular or hierarchical structure, such as the political and administrative partition of a country. In the context of these hierarchies, we focus on queries that search for inclusion, disjointness, and adjacency between regions. The proposed structures build upon compact planar graph embeddings, which show to have a good trade-off between space and time.engAtribución-NoComercial-SinDerivadas 3.0 Españahttp://creativecommons.org/licenses/by-nc-nd/3.0/es/Compact data structuresMulti-granular hierarchySpatial partitionTopological modeljournal articleopen access10.1016/j.ic.2023.105029