# Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees

May 2020 (Written: Apr 2020)

Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu:

International Symposium on Algorithms and Computation (ISAAC) 2020
Y. Cao, SW. Cheng, M. Li (eds.): ISAAC 2020, LIPIcs 181, Dagstuhl, 2020, pp 25:1–25:18

Succinct tree data structures represent an ordinal tree on $n$ nodes in $2n+o(n)$ bits of space while supporting many navigational operations in constant time (on a standard word-RAM); a list of these operations is given in Table 1 of the paper.
Since that amount of space is not enough to store a mapping from arbitrary identifiers to nodes of the tree, succinct trees refer to nodes by ids (operations $\texttt{node_rank}(v)$ and $\texttt{node_select}(i)$), which are solely defined based on the topology of the tree. A natural choice is to assign each node its position (“rank”) in a traversal of all nodes in the tree. The standard traversal algorithms are either depth-first traversals – preorder, postorder, inorder a.k.a. symmetric order – or breadth-first traversals (also called level order or heap order for trees).
All previously known succinct tree data structures either support $\texttt{node_rank}$ and $\texttt{node_select}$ for ids based on depth-first traversals, or support ids based on breadth-first traversals, but not both. In particular, mapping from level-order ranks to preorder ranks (and vice versa) was not efficiently possible. Using a novel tree partitioning scheme, tree slabbing, we design the first succinct tree data structure that supports this mapping in constant time.