Approximating the Bandwidth via Volume Respecting Embeddings (Preliminary Version 3)

A linear arrangement of an n-vertex graph is a one-to-one mapping of its vertices to the integers {1, ?, n}. The bandwidth of a linear arrangement is the maximum difference between mapped values of adjacent vertices. The problem of finding 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.