Compact Routing Schemes for Generalised Chordal Graphs

In this paper, we show how to use the notion of layering-tree introduced in [5], in order to obtain polynomial time constructible routing schemes. We describe efficient routing schemes for two classes of graphs that include the class of chordal graphs. For k-chordal graphs, i.e., graphs containing no induced cycle of length greater than k, the routing scheme uses addresses and local memories of size O(log 2 n) bits per node, and the length of the route between all pairs of vertices never exceeds their distance plus k + 1 (deviation at most k + 1). For tree-length δ graphs, i.e., graphs admitting a tree-decomposition in which the diameter of any bag is at most δ, the routing scheme uses addresses and local memories of size O(δ log 2 n) bits per node, and its deviation is at most 6δ 2. Observe that for chordal graphs, for which δ = 1 and k = 3, both schemes produce a deviation 4, with addresses and local memories of size O(log 2 n )b its per node.