Line-distortion, Bandwidth and Path-length of a graph
  We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson-Seymour's path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show:   - if a graph $G$ can be embedded into the line with distortion $k$, then $G$ admits a Robertson-Seymour's path-decomposition with bags of diameter at most $k$ in $G$;   - for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem;   - there is an efficient 2-approximation algorithm for computing the path-length of an arbitrary graph;   - AT-free graphs and some intersection families of graphs have path-length at most 2;   - for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem. 
Feodor F. Dragan and Ekkehard K\"ohler and Arne Leitert
cs.DS