How to Use Spanning Trees to Navigate in Graphs. Dragan, Xiang. FOCS 2009.

Investigates how to navigate graphs efficiently using the spanning tree T of a graph G

Navigation is done through knowledge of a nodes neighbors (or k-neighborhood) and T

In wireless networks, a common heuristic is to simply move packets to the neighbor that is geographically closest to the destination. Of course this scheme can run into problems so there are various methods to try and escape local optima

If geographic distances arent applicable or unkown, other similar methods measure location based on proximity to a number of “beacon” nodes. This usually works well in practice, but does not have theoretic guarantees

If however, an embedding of the spanning tree is used instead of beacons, delivery is guaranteed

Its possible to encode node labels compactly s.t. node distances can be found simply by comparing labels (of size log^2 n)

So minimum spanning tree routing can be done just with these particularly encoded labels and an adjacency list for each node

In some classes of graphs routing according to the MST will be optimal

There are two additional tree routing strategies (aside from the obvious one) that need a small amount of information for each node (logarithmic) that encodes how far up the spanning tree it is

These two strategies are “simpler and more compact” than the vanilla method, and in some cases the paths created will be shorter

The results are all for particular classes of graphs which I’m not going to investigate in particular