On compact and efficient routing in certain graph classes

In this paper we refine the notion of tree-decomposition by introducing acyclic (R,D)(R,D)-clustering, where clusters are subsets of vertices of a graph and R and D   are the maximum radius and the maximum diameter of these subsets. We design a routing scheme for graphs admitting induced acyclic (R,D)(R,D)-clustering where the induced radius and the induced diameter of each cluster are at most 2. We show that, by constructing a family of special spanning trees, one can achieve a routing scheme of deviation Δ⩽2RΔ⩽2R with labels of size O(log3n/loglogn) bits per vertex and O(1)O(1) routing protocol for these graphs. We investigate also some special graph classes admitting induced acyclic (R,D)(R,D)-clustering with induced radius and diameter less than or equal to 2, namely, chordal bipartite, homogeneously orderable, and interval graphs. We achieve the deviation Δ=1Δ=1 for interval graphs and Δ=2Δ=2 for chordal bipartite and homogeneously orderable graphs.