  Graphs with bounded highway dimension were introduced by Abraham et al. [SODA
2010] as a model of transportation networks. We show that any such graph can be
embedded into a distribution over bounded treewidth graphs with arbitrarily
small distortion. More concretely, given a weighted graph G = (V, E) of
constant highway dimension, we show how to randomly compute a weighted graph H
= (V, E') that distorts shortest path distances of G by at most a 1 +
${\varepsilon}$ factor in expectation, and whose treewidth is polylogarithmic
in the aspect ratio of G. Our probabilistic embedding implies quasi-polynomial
time approximation schemes for a number of optimization problems that naturally
arise in transportation networks, including Travelling Salesman, Steiner Tree,
and Facility Location.
  To construct our embedding for low highway dimension graphs we extend
Talwar's [STOC 2004] embedding of low doubling dimension metrics into bounded
treewidth graphs, which generalizes known results for Euclidean metrics. We add
several non-trivial ingredients to Talwar's techniques, and in particular
thoroughly analyse the structure of low highway dimension graphs. Thus we
demonstrate that the geometric toolkit used for Euclidean metrics extends
beyond the class of low doubling metrics.
