论文标题
如何在圆环上变形
How to Morph Graphs on the Torus
论文作者
论文摘要
我们将第一个算法介绍给圆环上的变形图。给定两个同位素在欧几里得扁平圆环上的同位素基本上是3相连的嵌入，其中两个图纸中的边缘都是测量学，我们的算法都计算从一个图形到另一台图的连续变形，因此所有边缘始终都是大地测量。以前，即使存在这种变体的存在也不为人所知。我们的算法以$ O（n^{1+ω/2}）$时间运行，其中$ω$是矩阵乘法指数，计算出的变体由$ o（n）$平行线性变形步骤组成。现有的用于变形平面直线图的技术不会立即概括为圆环上的图形；尤其是，凯恩斯（Cairns）的原始1944年证明及其最新的改进取决于每个平面图最多都包含一个程度的顶点。我们的证明依赖于对圆环的6个常规三角剖分的微妙几何分析。我们还大量使用了Tutte的春季嵌入定理到圆环图的自然扩展。
We present the first algorithm to morph graphs on the torus. Given two isotopic essentially 3-connected embeddings of the same graph on the Euclidean flat torus, where the edges in both drawings are geodesics, our algorithm computes a continuous deformation from one drawing to the other, such that all edges are geodesics at all times. Previously even the existence of such a morph was not known. Our algorithm runs in $O(n^{1+ω/2})$ time, where $ω$ is the matrix multiplication exponent, and the computed morph consists of $O(n)$ parallel linear morphing steps. Existing techniques for morphing planar straight-line graphs do not immediately generalize to graphs on the torus; in particular, Cairns' original 1944 proof and its more recent improvements rely on the fact that every planar graph contains a vertex of degree at most 5. Our proof relies on a subtle geometric analysis of 6-regular triangulations of the torus. We also make heavy use of a natural extension of Tutte's spring embedding theorem to torus graphs.
