Succinct Encoding of Binary Strings Representing Triangulations
Ver/ abrir
Use este enlace para citar
http://hdl.handle.net/2183/37796Coleccións
- GI-LBD - Artigos [54]
Metadatos
Mostrar o rexistro completo do ítemTítulo
Succinct Encoding of Binary Strings Representing TriangulationsData
2021-11Cita bibliográfica
Fuentes-Sepúlveda, J., Seco, D. & Viaña, R. Succinct Encoding of Binary Strings Representing Triangulations. Algorithmica 83, 3432–3468 (2021). https://doi.org/10.1007/s00453-021-00861-4
Resumo
[Abstract]: We consider the problem of designing a succinct data structure for representing the connectivity of planar triangulations. The main result is a new succinct encoding achieving the information-theory optimal bound of 3.24 bits per vertex, while allowing efficient navigation. Our representation is based on the bijection of Poulalhon and Schaeffer (Algorithmica, 46(3):505–527, 2006) that defines a mapping between planar triangulations and a special class of spanning trees, called PS-trees. The proposed solution differs from previous approaches in that operations in planar triangulations are reduced to operations in particular parentheses sequences encoding PS-trees. Existing methods to handle balanced parentheses sequences have to be combined and extended to operate on such specific sequences, essentially for retrieving matching elements. The new encoding supports extracting the d neighbors of a query vertex in O(d) time and testing adjacency between two vertices in O(1) time. Additionally, we provide an implementation of our proposed data structure. In the experimental evaluation, our representation reaches up to 7.35 bits per vertex, improving the space usage of state-of-the-art implementations for planar embeddings.
Palabras chave
Connectivity compression
Planar triangulation
Succinct encoding
Planar triangulation
Succinct encoding
Descrición
Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature
Versión do editor
Dereitos
Atribución 3.0 España