A linear arrangement of an n-vertex graph is a one-to-one mapping of its vertices to the integers f1; : : : ; ng. The bandwidth of a linear arrangement is the maximum di erence between mapped values of adjacent vertices. The problem of nding a linear arrangement with smallest possible bandwidth in NP-hard. We present a randomized algorithm that runs in nearly linear time and outputs a linear arrangement whose bandwidth is within a polylogarithmic multiplicative factor of optimal. Our algorithm is based on a new notion, called volume respecting embeddings, which is a natural extension of small distortion embeddings of Bourgain and of Linial, London and Rabinovich.
The analysis of all these algorithms is based on the notion of volume respecting embeddings that was introduced in REF .
Approximating the Bandwidth via Volume Respecting Embeddings
J. Comput. Syst. Sci.
Mathematics Computer Science