#### Summary of results and connections to prior work

- 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 -vertex graph which supports
exact distance labels with -bit labels
also supports compact routing with -bit
headers and -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

#### Techniques

- The paper uses a cool trick for reducing general graphs to
graphs that have maximum degree .

#### Ideas

- 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