  Tutte's spring embedding theorem states that, for a three-connected planar
graph, if the outer face of the graph is fixed as the complement of some convex
region in the plane, and all other vertices are placed at the mass center of
their neighbors, then this results in a unique embedding, and this embedding is
planar. It also follows fairly quickly that this embedding minimizes the sum of
squared edge lengths, conditional on the embedding of the outer face. However,
it is not at all clear how to embed this outer face. We consider the
minimization problem of embedding this outer face, up to some normalization, so
that the sum of squared edge lengths is minimized. In this work, we show the
connection between this optimization problem and the Schur complement of the
graph Laplacian with respect to the interior vertices. We prove a number of
discrete trace theorems, and, using these new results, show the spectral
equivalence of this Schur complement with the boundary Laplacian to the
one-half power for a large class of graphs. Using this result, we give
theoretical guarantees for this optimization problem, which motivates an
algorithm to embed the outer face of a spring embedding.

Combinatorics