标题： 曲面上Tutte重心嵌入的离散模拟 显示英文标题

标题： A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces

摘要： 图灵著名的重心嵌入定理描述了一种自然的方法来构建（3连通）平面图的直线嵌入（无交叉的绘制）：将外面对应的顶点映射到凸多边形的顶点，并确保每个剩余顶点处于凸位置，即其邻接顶点的重心，且系数为正。 实际计算嵌入则转化为求解一个线性方程组。 这种方法的一个特别吸引人的特点是通过选择重心权重所给予的灵活性。 图灵定理在非正曲率表面上的推广是已知的，但由于它们本质上是连续的，因此不会导致算法。 在本文中，我们提出了一种纯粹离散的图灵定理的类比，适用于非正曲率的表面（有边界或无边界），基于最近引入的减少三角剖分的概念。 我们在这种情况下证明了一个图灵定理：每一个与嵌入同伦的绘制，其中每个顶点都是和谐的（处于凸位置的离散类比），是一个弱嵌入（可以任意接近于嵌入）。 我们还提供了一个多项式时间算法，可以在不增加任何边长度的情况下使输入绘制变得和谐，类似于在不增加边长度的情况下使绘制处于凸位置。 显示英文摘要

摘要： Tutte's celebrated barycentric embedding theorem describes a natural way to build straight-line embeddings (crossing-free drawings) of a (3-connected) planar graph: map the vertices of the outer face to the vertices of a convex polygon, and ensure that each remaining vertex is in convex position, namely, a barycenter with positive coefficients of its neighbors. Actually computing an embedding then boils down to solving a system of linear equations. A particularly appealing feature of this method is the flexibility given by the choice of the barycentric weights. Generalizations of Tutte's theorem to surfaces of nonpositive curvature are known, but due to their inherently continuous nature, they do not lead to an algorithm. In this paper, we propose a purely discrete analog of Tutte's theorem for surfaces (with or without boundary) of nonpositive curvature, based on the recently introduced notion of reducing triangulations. We prove a Tutte theorem in this setting: every drawing homotopic to an embedding such that each vertex is harmonious (a discrete analog of being in convex position) is a weak embedding (arbitrarily close to an embedding). We also provide a polynomial-time algorithm to make an input drawing harmonious without increasing the length of any edge, in a similar way as a drawing can be put in convex position without increasing the edge lengths.