Search-space size in contraction hierarchies

We show that, under a worst-case assumption on the edge lengths, our bounds are comparable to those in the recent paper “VC-Dimension and Shortest Path Algorithms” of Abraham et al. [1], whose analysis depends also on the edge lengths. As a side result, we link their notion of highway dimension (a parameter that is conjectured to be small, but is unknown for all practical instances) with the notion of pathwidth. This is the first relation of highway dimension with a well-known graph parameter.