论文标题
离散跟踪定理和能量最小化平面图的弹簧嵌入
Discrete Trace Theorems and Energy Minimizing Spring Embeddings of Planar Graphs
论文作者
论文摘要
Tutte的弹簧嵌入定理指出，对于三个连接的平面图，如果图形的外表面作为平面中某些凸区域的补充，并且所有其他顶点都放在邻居的质量中心，则将其放置在其唯一的嵌入中，并且该嵌入为平面。同样很快就可以很快地嵌入，这可以最大程度地减少平方边缘长度的总和，这是在外部脸部嵌入的条件下。但是，尚不清楚如何嵌入外表面。我们考虑将外表嵌入到一些归一化的最小化问题，以便将平方边缘长度的总和最小化。在这项工作中，我们显示了此优化问题与图形拉普拉斯元素相对于内部顶点的schur补充之间的联系。我们证明了许多离散的跟踪定理，并使用这些新结果表明了该schur与边界拉普拉斯元素与大型图的一半功率相称的光谱等效性。使用此结果，我们为这种优化问题提供了理论保证，这激发了算法嵌入弹簧嵌入的外表面。
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.
