This paper mainly addresses the problem of efficiently labeling graphs in such a way that the distance between two nodes of the graph can be computed only from their labels. Of course, it is desirable to have the maximum length of a label be “short,” for example poly-logarithmic in the size of the graph, and have the labels be computable in, say, poly-logarithmic time. A distance labeling algorithm such as this can be used in a variety of network applications. The paper outlines a few, such as “memory-free” routing schemes, and provides references to others.

The authors present upper and lower bounds for the family of general graphs, and then find better results for restricted classes of graphs, such as bipartite graphs, unweighted binary trees, bounded degree planar graphs, and graphs of a certain maximum degree. Then they consider the time complexity of finding these labels for arbitrary input graphs. Finally, they list a number of open problems related to this area of research. Proofs in this paper are detailed, yet readable. The use of notation is not overwhelming, and explanations are sufficient to follow the logic. A couple of good diagrams round out the information, for additional clarity.