Tree skeletons: visualize all your possible trips
This is part of the Road/Transportation network at Gang (contact).
Hub labeling
The results presented here provide an explanation for the existence of efficient hub labeling in road networks (Abraham, Delling, Fiat, Goldberg and Werneck, 2010-2016). Pre-computing small hub sets for each node allows to answer distance queries in few micro-seconds on continent scale road networks (shortest path queries can be answered within a milli-second). To enable this the hub sets are sets of nodes that must have the following covering property: any pair of nodes must have a common hub on a shortest path joining them. The efficiency of the method relies on finding small hub sets with the covering property. This can be explained by observing tree skeletons as described bellow.
Tree skeleton
A tree skeleton is obtained by drawing the first two-third of all shortest paths from a given source node s to any other node in the network. Click on the image bellow to zoom in some tree skeletons. Drawing complete shortest paths would result in covering completely the map, but road networks have the property that paths share few long prefixes. Appropriate random sampling in each tree skeleton allows to compute hub sets of size O(k log D) with the covering property [4] where k (the skeleton dimension) is the maximum number of branches of a skeleton tree that cross a given distance range, and D is the (integral) diameter (maximum distance to minimum distance ratio).
Highway dimension
The concept of skeleton dimension was inspired by that of highway dimension (Abraham, Delling, Fiat, Goldberg and Werneck, 2010-2016). A graph has highway dimension h if the set of shortest paths of length greater than r/2 that intersect a ball of radius r has a hitting set of at most h nodes for all radii r and ball centers. Small highway dimension implies the existence of small hub sets with the covering property. As any graph with highway dimension h has skeleton dimension k ≤ h, the present work on skeleton dimension can be seen as a generalization of previous work on highway dimension. There is also a separation as grid like networks can have skeleton dimension O(log n) while having highway dimension Θ(n1/2).
Papers
