Hardness and approximation of minimum distortion embeddings

We show that the problem of computing a minimum distortion embedding of a given graph into a path is NP-hard when the input graph is bipartite, cobipartite, or split. This problem is hard to approximate within a constant factor on arbitrary graphs. We give polynomial-time constant-factor approximation algorithms for split, cocomparability, interval and cographs.