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

| read here | PDF | DOI | arXiv |

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).

Example of mapping between BFS and DFS ranks in a tree — An example of the mapping between BFS and DFS ranks in an ordinal tree.

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.