Navigating planar topologies in near-optimal space and time
Use este enlace para citar
http://hdl.handle.net/2183/37821
A non ser que se indique outra cousa, a licenza do ítem descríbese como Atribución-NoComercial-SinDerivadas 3.0 España
Coleccións
- OpenAIRE [366]
- GI-LBD - Artigos [54]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Navigating planar topologies in near-optimal space and timeData
2023-02Cita bibliográfica
J. 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.101922
Resumo
[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.
Palabras chave
Planar graphs
Succinct data structures
Topology queries
Succinct data structures
Topology queries
Descrición
©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.101922 Versión aceptada
Versión do editor
Dereitos
Atribución-NoComercial-SinDerivadas 3.0 España
ISSN
0925-7721