- INSTANCE:
Graph
.
- SOLUTION:
A one-to-one function
].
- MEASURE:
The total length of the edges in the linear arrangement, i.e.
.

*Good News:*Approximable within [416].*Comment:*Admits a PTAS if . Variation in which the*n*points are on the*d*-dimensional grid instead of in a line and the rectilinear metric is used also admits a PTAS if [36].*Garey and Johnson:*GT42