An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5n+o(n). This is the first algorithm breaking the trivial n!-barrier.