Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees
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.
We then use this data structure as the basis for succinct distance oracles for interval graphs and related graph classes.