Representation of short distances in structurally sparse graphs

A partial orientation ~H of a graph G is a weak r -guidance system if for any two vertices at distance at most r in G , there exists a shortest path P between them such that ~H directs all but one edge in P towards this edge. In case ~H has bounded maximum outdegree, this gives an eﬃcient representation of shortest paths of length at most r in G . We show that graphs from many natural graph classes admit such weak guidance systems, and study the algorithmic aspects of this notion.