We present an algorithm for finding shortest surface non-separating cycles in graphs with given edge-lengths that are embedded on surfaces. The time complexity is O(g~(3/2)V~(3/2) log V + g~(5/2)V~(1/2)), where V is the number of vertices in the graph and g is the genus of the surface. If g = o(V~(1/3-ε)), this represents a considerable improvement over previous results by Thomassen, and Erickson and Har-Peled. We also give algorithms to find a shortest non-contractible cycle in O(g~(O(g)) V~(3/2)) time, improving previous results for fixed genus. This result can be applied for computing the (non-separating) face-width of embedded graphs. Using similar ideas we provide the first near-linear running time algorithm for computing the face-width of a graph embedded on the projective plane, and an algorithm to find the face-width of embedded toroidal graphs in O(V~(5/4) log V) time.
展开▼
机译：我们提出了一种用于在嵌入在表面上的给定边缘长度的图表中找到最短表面非分离周期的算法。时间复杂性是O（g〜（3/2）V〜（3/2）log v + g〜（5/2）v〜（1/2）），其中V是图中的顶点数量g是表面的属。如果g = o（v〜（1/3-ε）），这代表了汤斯森和埃里克森和埃克森的结果相当大的改进。我们还提供算法，以找到o（g〜（g））v〜（3/2））时间，改善固定属的先前结果。该结果可以应用于计算嵌入图的（非分离）面部宽度。使用类似的想法，我们提供了第一种近线性运行时间算法，用于计算嵌入在投影平面上的图形的面宽，以及找到O（V〜（5/4的嵌入环形图的面宽度的算法log v）时间。
展开▼
