Improved Bandwidth Approximation for Trees and Chordal Graphs

A linear arrangement of an n-vertex graph G = (V, E) is a one-one mapping f of the vertex set V onto the set [n] = {0, 1, . . . , n - 1}. The bandwidth of this linear arrangement is the maximum difference between the images of the endpoints of any edge in E(G). When the input graph G is a tree, the best known approximation algorithms for the minimum bandwidth linear arrangement (which are based on the principle of volume respecting embeddings) output a linear arrangement which has bandwidth within O(log³ n) of the optimal bandwidth. In this paper, we present a simple randomized O(log^2.5 n)-approximation algorithm for bandwidth minimization on trees. We also show that a close variant of this algorithm gives a similar performance guarantee for chordal graphs.