The highway dimension is a graph parameter modelling transportation networks, such as road networks or public transportation networks. It was first formally defined by Abraham et al. based on the observation by Bast et al. that any road network has a sparse set of "transit nodes", such that driving from a point A to a sufficiently far away point B along the shortest route will always pass through one of these transit nodes. It has also been proposed that the highway dimension captures the properties of public transportation networks well, given that longer routes using busses, trains, or airplanes will typically be serviced by larger transit hubs (stations and airports). This relates to the spoke–hub distribution paradigm in transport topology optimization.
Definitions Several definitions of the highway dimension exist, although the one based on approximate shortest paths given below is the most general one. Each definition of the highway dimension uses a hitting set of a certain set of (approximate) shortest paths: given a graph G = ( V , E ) {\displaystyle G=(V,E)} with edge lengths ℓ : E → R + {\displaystyle \ell :E\to \mathbb {R} ^{+}} , let P {\displaystyle {\mathcal {P}}} contain every vertex set P ⊆ V {\displaystyle P\subseteq V} such that P {\displaystyle P} induces a shortest path between some vertex pair of G {\displaystyle G} , according to the edge lengths ℓ {\displaystyle \ell } . To measure the highway dimension we determine the "sparseness" of a hitting set of a subset of P {\displaystyle {\mathcal {P}}} in a local area of the graph, for which we define a ball of radius r > 0 {\displaystyle r>0} around a vertex u ∈ V {\displaystyle u\in V} to be the set B r ( u ) ⊆ V {\displaystyle B_{r}(u)\subseteq V} of vertices at distance at most r {\displaystyle r} from u {\displaystyle u} in G {\displaystyle G} according to the edge lengths ℓ {\displaystyle \ell } . In the context of low highway dimension graphs, the vertices of a hitting set for the shortest paths are called hubs.
Definition 1 The original definition of the highway dimension measures the sparseness of a hub set H {\displaystyle H} of shortest paths contained within a ball of radius 4 r {\displaystyle 4r} :The highway dimension of G {\displaystyle G} is the smallest integer h 1 {\displaystyle h_{1}} such that for any radius r > 0 {\displaystyle r>0} and any node u ∈ V {\displaystyle u\in V} there is a hitting set H ⊆ B 4 r ( u ) {\displaystyle H\subseteq B_{4r}(u)} of size at most h 1 {\displaystyle h_{1}} for all shortest paths P ∈ P {\displaystyle P\in {\mathcal {P}}} of length more than r {\displaystyle r} for which P ⊆ B 4 r ( u ) {\displaystyle P\subseteq B_{4r}(u)} .A variant of this definition uses balls of radius c r {\displaystyle cr} for some constant c > 4 {\displaystyle c>4} . Choosing a constant greater than 4 implies additional structural properties of graphs of bounded highway dimension, which can be exploited algorithmically.
… excerpt ends here. Continue reading the full article.
