Discrete trace theorems and energy minimizing spring embeddings of planar graphs
Discrete trace theorems and energy minimizing spring embeddings of planar graphs
复制标题
平面图的离散迹定理和能量最小化弹簧嵌入
DOI：
10.1016/j.laa.2020.08.035
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Zikatanov, Ludmil T.
中科院分区：
文献类型：
--
作者：
Urschel, John C.;Zikatanov, Ludmil T.
Tutte的弹簧嵌入定理指出，对于一个三连通平面图，如果图的外表面固定为平面上某个凸域的补边，并且所有其他顶点都位于其相邻顶点的质心，则这将导致唯一的嵌入，并且这种嵌入是平面的。这也是相当快的，这种嵌入最小化平方边长度的和，条件是嵌入外表面。然而，完全不清楚如何嵌入这个外表面。我们考虑嵌入这个外表面的最小化问题，直到达到一定的归一化，从而使平方边长度的和最小化。在这项工作中，我们证明了这个最优化问题与图的关于内部顶点的拉普拉斯的Schur补之间的联系。我们证明了一些离散迹定理，并利用这些新结果证明了对于一大类图，这种Schur补与边界拉普拉斯的1/2次方的谱等价。利用这一结果，我们给出了这个优化问题的理论保证，该优化问题激励了一个嵌入弹簧外表面的算法。
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.
登录
查看更多内容
DOI：
10.1515/rnam.1991.6.3.223
发表时间：
1991
期刊：
--
影响因子：
--
作者：
S. V. Nepomnyaschikh
通讯作者：
S. V. Nepomnyaschikh
DOI：
10.1007/3-540-45071-8_50
发表时间：
2003-07
期刊：
--
影响因子：
--
作者：
Y. Koren
通讯作者：
Y. Koren
不定Stekloff算子特征值逼近的傅里叶方法
DOI：
10.1007/978-3-319-97136-0_3
发表时间：
2018
期刊：
Lecture notes in computer science
影响因子：
--
作者：
Wu, Yangqingxiang;Zikatanov, Ludmil T
通讯作者：
Zikatanov, Ludmil T
舒尔补语
DOI：
10.1002/9781119140542.app2
发表时间：
2018
期刊：
Finite-Time Stability
影响因子：
--
作者：
J. W. Nunn;J. Chipman
通讯作者：
J. Chipman
影响因子：
2.9
作者：
Koren, Y
通讯作者：
Koren, Y