Line-Distortion, Bandwidth and Path-Length of a Graph.

For a graph $$G=(V,E)$$ the minimum line-distortion problem asks for the minimum k such that there is a mapping f of the vertices into points of the line such that for each pair of vertices x, y the distance on the line $$|f(x) - f(y)|$$ can be bounded by the term $$d_G(x, y)\le |f(x)-f(y)|\le k \, d_G(x, y)$$ , where $$d_G(x, y)$$ is the distance in the graph. The minimum bandwidth problem minimizes the term $$\max _{uv\in E}|f(u)-f(v)|$$ , where f is a mapping of the vertices of G into the integers $$\{1, \ldots , n\}$$ . 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: [ABSTRACT FROM AUTHOR]