Fuentes Sepúlveda, JoséNavarro, GonzaloSeco, Diego2024-07-092024-07-092023-02J. Fuentes-Sepúlveda, G. Navarro, and D. Seco, "Navigating planar topologies in near-optimal space and time", Computational Geometry: Theory and Applications, Vol. 109, article 101922, Feb. 2023, doi: 10.1016/j.comgeo.2022.1019220925-7721http://hdl.handle.net/2183/37821©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.comgeo.2022.101922Versión aceptada[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 ω(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.engAtribución-NoComercial-SinDerivadas 3.0 Españahttp://creativecommons.org/licenses/by-nc-nd/3.0/es/Planar graphsSuccinct data structuresTopology queriesjournal articleopen access10.1016/j.comgeo.2022.101922