A Practical Succinct Dynamic Graph Representation
Miguel E. Coimbra, Joana Hrotkó, Alexandre P. Francisco,
Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, and
We address the problem of representing dynamic graphs using k^2-trees.
The k^2-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
In this paper we present a k^2-tree based implementation which follows
instead the ideas by Munro et al. (PODS 2015) to circumvent this
We present two dynamic graph k^2-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