Prior: Already known that graphs with constant-sized separators (trees, outerplanar, series-parallel, bounded tree-width) support exact distance labels and no-stretch compact routing schemes
Prior: But, also known that there are classes of graphs without constant-sized separators that admit exact distance labels
Result: Every $n$ -vertex graph which supports exact distance labels with $O(l(n))$ -bit labels also supports compact routing with $O(l(n)+\\log^2 n)$ -bit headers and $O(\\sqrt{n}(l(n)+\\log^2n))$ -bit tables and additive stretch 6.
Result: For interval graphs and circular arc graphs (neither of which admits constant-size separators), the above result can be improved to additive stretch 1

The paper uses a cool trick for reducing general graphs to graphs that have maximum degree $\\sqrt{n}$ .

It is worth checking whether the above families of graphs admit concise hyperbolic greedy embeddings, similarly to the case of trees
Check whether the degree reduction trick (above) can be replaced with a sparsification argument