  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.
