Compact routing schemes for bounded tree-length graphs and for k-chordal graphs

In this paper we show how to use the notion of layering-tree introduced in [5], in order to construct efficient routing schemes. We obtain a routing scheme polynomial time constructible for tree-length delta graphs, i.e., graphs admitting a tree-decomposition with small diameter bags. This routing scheme uses address and local memory of size 0 (deltalog(2) n) bits, and for all pairs of nodes, the length of the route never exceed their distance plus 6delta-2 (deviation at most 6delta-2). Then we adapt our routing scheme for k-chordal graphs. In this later case, we obtain a deviation k + 1, with addresses and local memories of size 0(log(2) n) bits per node, an improvement on the best previous to date. Observe that for chordal graphs, for which delta = 1 and k = 3, the both schemes produce a deviation 4, with addresses and local memories of size 0(log(2) 71) bits per node, also an improvement on the best previous.