Contributions:

1. Optimally concise routing schemes for trees are described
2. Optimal center selection for Cowen's routing scheme is described, which combined with tighter label encoding produces optimal routing schems for stretch 3
3. Routing schemes for tree covers are described, producing almost optimal schemes for stretch 4k-5 and any integer k greater than 0

Techniques:

• Kraft's inequality for some lower bounds
• Arithmetic coding for optimal encodings of number series
• Two different types of heavy-path decomposition of trees

Ideas:

• The Cowen decomposition induces a tree relationship between the whole graph (the root), the centers (children of the root), and each center's pcoket of vertices (the children of the children). Then the label sizes are improved (in this paper) by selecting the centers more cleverly and using a tight encoding of the routes along the induced tree. Consider generalizing Cowen's decomposition to allow producing arbitrary induced trees. This may address the open problem at the end of this paper.
• Cowen's routing scheme has worst case label size even for nice graphs like expanders and scale-free. Are there methods that take advantage of graph's conductance? Perhaps Thorup and Zwick's tree cover method?
• Check of there is a similarity between the tree decompositions here and van Emde Boas queues.