Compact Routing Schemes for Generalised Chordal Graphs

Abstract

In this paper, we show how to use the notion of layering-tree introduced in [], 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² 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² 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² n) bits per node.