Coimbra, Miguel E.Hrotkó, JoanaFrancisco, Alexandre P.Russo, Luís M.S.Bernardo, Guillermo deLadra, SusanaNavarro, Gonzalo2024-11-182024-11-182022-05M. E. Coimbra, J. Hrotkó, A.P. Francisco, L.M.S. Russo, G. de Bernardo, S.Ladra, and G. Navarro, "A practical succinct dynamic graph representation", Information and Computation, Vol. 285, Part B, May 2022, 104862, https://doi.org/10.1016/j.ic.2021.1048620890-5401http://hdl.handle.net/2183/40153©2022 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.2021.104862[Abstract]: We address the problem of representing dynamic graphs using k2-trees. The k2-tree data structure is one of the succinct data structures proposed for representing static graphs, and binary relations in general. It relies on compact representations of bit vectors. Hence, by relying on compact representations of dynamic bit vectors, we can also represent dynamic graphs. However, this approach suffers of a well known bottleneck in compressed dynamic indexing. In this paper we present a k2-tree based implementation which follows instead the ideas by Munro et al. (PODS 2015) to circumvent this bottleneck. We present two dynamic graph k2-tree implementations, one as a standalone implementation and another as a C++ library. The library includes efficient edge and neighbourhood iterators, as well as some illustrative algorithms. Our experimental results show that these implementations are competitive in practice.engAtribución-NoComercial-SinDerivadas 4.0 International (CC BY-NC-ND)http://creativecommons.org/licenses/by-nc-nd/3.0/es/Compact graph representationsDynamic graphsGraph libraryk2-treejournal articleopen access10.1016/j.ic.2021.104862