Before revision:  It also provides constant-time support for all the operations provided by different approaches in previous work, as well as new operations that allow us to retrieve the last internal node before or the firstinternal node after a given node in a level-order traversal .
After revision:  Our distance oracles for interval graphs also support navigation queries -- testing adjacency, computing node degrees, neighborhoods, and shortest paths -- all in optimal time. Our technique also yields optimal distance oracles for proper interval graphs (unit-interval graphs) and circular-arc graphs. Our tree data structure supports all operations provided by different approaches in previous work, as well as new operations that allow us to retrieve the last internal node before or the firstinternal node after a given node in a level-order traversal .