2020/01/29 by John Urschel, Ludmil Zikatanov, Urschel, John C. +1
Computer Science · Materials Science · #05C50 #05C62 #05C85 #15A18 #Advanced Graph Theory Research #Carbon and Quantum Dots Applications #Combinatorics (math.CO) #Dendrimers and Hyperbranched Polymers #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2001.10928
openalex publication_date 2020/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Tutte's spring embedding theorem states that, for a three-connected planar\ngraph, if the outer face of the graph is fixed as the complement of some convex\nregion in the plane, and all other vertices are placed at the mass center of\ntheir neighbors, then this results in a unique embedding, and this embedding is\nplanar. It also follows fairly quickly that this embedding minimizes the sum of\nsquared edge lengths, conditional on the embedding of the outer face. However,\nit is not at all clear how to embed this outer face. We consider the\nminimization problem of embedding this outer face, up to some normalization, so\nthat the sum of squared edge lengths is minimized. In this work, we show the\nconnection between this optimization problem and the Schur complement of the\ngraph Laplacian with respect to the interior vertices. We prove a number of\ndiscrete trace theorems, and, using these new results, show the spectral\nequivalence of this Schur complement with the boundary Laplacian to the\none-half power for a large class of graphs. Using this result, we give\ntheoretical guarantees for this optimization problem, which motivates an\nalgorithm to embed the outer face of a spring embedding.\n