  Visualizing graphs using virtual physical models is probably the most heavily
used technique for drawing graphs in practice. There are many algorithms that
are efficient and produce high-quality layouts. If one requires that the layout
also respect a given set of non-uniform edge lengths, however, force-based
approaches become problematic while energy-based layouts become intractable. In
this paper, we propose a reformulation of the stress function into a two-part
convex objective function to which we can apply semi-definite programming
(SDP). We avoid the high computational cost associated with SDP by a novel,
compact re-parameterization of the objective function using the eigenvectors of
the graph Laplacian. This sparse representation makes our approach scalable. We
provide experimental results to show that this method scales well and produces
reasonable layouts while dealing with the edge length constraints.
