Graph spanners are sparse subgraphs that preserve distances between nodes of the original graph to an approximation that is bounded, usually given in the form of a multiplication factor known as stretch. Such spanners have application in distance oracles, for labeling nodes to quickly compute short paths between nodes, for routing in networks and in solving linear systems, and so on. A conjecture by Erdos [1] characterizes the tradeoff between the spanner sparseness and the multiplicative stretch.

Here, two new data structures are introduced that report paths in undirected graphs, with query time proportional to the length of the paths. The first one applies to weighted graphs whose diameters are polynomially bounded in the number of nodes, and the second one applies only to unweighted graphs. Another interesting contribution of this paper is the consideration of graphs that exclude a minor. The authors claim their schemes improve over the complexity of earlier reported algorithms for all of these problems.

Starting with an algorithm to construct sparse covers that makes use of clusters of balls of nodes, the authors provide a distance labeling scheme that can also serve as a path reporting distance oracle that is built from a collection of sparse covers. Following the same framework, the distance labels are extended to a compact routing scheme where vertices have a short label and store a routing table. For the special case of unweighted graphs, a variation of the previously known Thorup–Zwick distance oracle is used in the construction, resulting in a path reporting distance oracle of improved stretch.

The paper is well written and well organized. The first two sections introduce the problems and briefly provide the preliminaries, with adequate references. In addition to the core contributions that include various theorems and proofs, the paper also suggests open problems for further research. Overall, this is an impressive paper, and the presentation style is very delightful.