A $(1 + {\varepsilon})$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs

Understand

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.