We consider the problem of finding a planar embedding of a graph at fixed vertex locations that minimizes the total edge length. The problem is known to be NP-hard. We give polynomial time algorithms achieving an    $O\sqrt{n} \log n$    approximation for paths and matchings, and an On approximation for general graphs.
['Timothy M. Chan', 'Hella-Franziska Hoffmann', 'Stephen Kiazyk', 'Anna Lubiw']
Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations