Succinct Euler-Tour Trees

We show how to maintain unrooted ordered trees in succinct space under the operations of linking trees (by adding an edge) and cutting trees (by deleting an edge), while supporting various queries.

The trees are represented by their Euler tour stored in a macro tree of micro trees. A collection of Euler-tour trees for a forest on $n$ vertices can be stored in $2n + o(n)$ bits such that simple queries take constant time, more complex queries take logarithmic time and updates take polylogarithmic amortized time.

CCCG does not publish proceedings with a publisher, but they are available online: CCCG 2021 Proceedings.