# Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

arXiv: https://arxiv.org/abs/1609.00512 · HTML: https://mlsanity.com/paper/1609.00512/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2016.

## Built on by (most cited first, 1 of 1)

- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)

## Abstract (arXiv)

The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) subseteq V to each node u ∈ V, in such a way that for any pair of nodes u, v, the intersection of hub sets S(u) cap S(v) contains a node on the shortest uv-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least r intersecting a given ball of radius 2r. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.