On compact and efficient routing in certain graph classes Original Research Article

In this paper we refine the notion of tree-decomposition by introducing acyclic image-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 image-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 image with labels of size image bits per vertex and image routing protocol for these graphs. We investigate also some special graph classes admitting induced acyclic image-clustering with induced radius and diameter less than or equal to 2, namely, chordal bipartite, homogeneously orderable, and interval graphs. We achieve the deviation image for interval graphs and image for chordal bipartite and homogeneously orderable graphs.