A Discrete Analog of Tutte’s Barycentric Embeddings on Surfaces The conference version of this paper was published in SODA 2025.
Éric Colin de Verdière, Vincent Despré, Loïc Dubois · 2025
Read A Discrete Analog of Tutte’s Barycentric Embeddings on Surfaces The conference version of this paper was published in SODA 2025. by Éric Colin de Verdière, Vincent Despré, Loïc Dubois (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13096.txt.
Introduction
Éric Colin de Verdière, Vincent Despré, and Loïc Dubois gave a discrete version of Tutte's classic graph drawing theorem for surfaces in 2025. Tutte showed how to draw a planar graph without crossings: fix the outer face as a round polygon and set each inner vertex at the balance point of its neighbors. Solving a linear system then yields the drawing.
Versions for curved surfaces existed but led to no algorithm. The authors use a newer notion of reducing triangulations to build a purely discrete analog. They prove that a drawing in which each vertex is harmonious, their discrete balance notion, is a weak embedding. An algorithm makes any input drawing harmonious without lengthening edges, in polynomial time.
Catalog record
| CREATOR | Éric Colin de Verdière, Vincent Despré, Loïc Dubois |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 125 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13096
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Discrete Analog of Tutte’s Barycentric Embeddings on Surfaces The conference version of this paper was published in SODA 2025. Éric Colin de Verdière, Vincent Despré, Loïc Dubois Abstract 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. 1 Introduction Tutte’s barycentric method and its generalizations. One of the most basic problems in graph drawing is that of constructing straight-line embeddings (crossing-free drawings) of planar graphs [ 33 ] . Tutte’s celebrated barycentric embedding theorem [ 32 ] (1963) lies at the root of the wide class of force-directed drawing algorithms [ 26 ] . It provides a remarkably simple method to build straight-line embeddings of a (simple, 3-connected) planar graph, assuming the knowledge of a facial cycle in some (topological) planar embedding: map the vertices of that cycle to the vertices of a convex polygon, in the same order, and locate the other vertices in such a way that, if the inner edges are replaced by springs, then this physical system is at its equilibrium. Tutte’s initial proof [ 32 ] has been revisited many times; see, in particular, Richter-Gebert [ 29 , Section 12.2] , Thomassen [ 31 ] , or Edelsbrunner [ 11 , Section I.4] , thus leading to more insight. As it turns out, it suffices that each inner vertex be a barycenter of its neighbors, with some arbitrary positive coefficients [ 18 ] . (The coefficients need not be symmetric, so this is more general than requiring an equilibrium in a spring system, even if the springs may have different rigidities.) For this reason, Tutte drawings are called barycentric , and they can be computed by solving a system of linear equations. Equivalently, it suffices that each vertex be in convex position with respect to its neighbors: disregarding some degenerate cases, every straight line containing an inner vertex v sees edges incident to v on both sides. (The 3-connectivity assumption avoids overlaps.) Tutte’s method has been seminal not only for graph drawing. Floater and Gotsman [ 19 ] and Gotsman and Surazhsky [ 22 ] use it to build morphings between two straight-line embeddings of the same planar graph. In a nutshell, one can interpolate between two embeddings in convex position by moving the barycentric coefficients from those of the initial embedding to those of the final embedding; Tutte’s theorem guarantees that the drawing will be an embedding at every step. Other applications include surface parameterization and approximation [ 18 ] . Of special interest to us is a particular generalization of Tutte’s theorem to graphs drawn on a surface S without boundary and of non-positive curvature (in particular, such surfaces are not homeomorphic to a sphere). Consider a graph G embedded as (the 1-skeleton of) a triangulation of S (the embedding needs not be geodesic). Y. Colin de Verdière [ 5 , Théorème 2] (see also Hass and Scott [ 25 , Lemma 10.12] and Luo, Wu, and Zhu [ 28 , Theorem 1.6] ) proves that if this embedding is deformed by a homotopy (a continuous motion) in such a way that each edge is geodesic and each vertex is in convex position, then it is actually an embedding. A similar result holds for surfaces with boundary [ 5 , Théorème 3] , fixing part of the triangulation to the boundary. Without the requirement to have a triangulation, degenerate cases could occur, so one would not always get an embedding. The assumption on non-positive curvature seems necessary because it ensures that geodesics (locally shortest paths) cross minimally. As a side note, for the special case of the torus, other graph embedding methods based on Schnyder woods exist [ 20 ] , but they lack the flexibility of barycentric embeddings, and to our knowledge they have not been extended to higher genus. Towards a discrete version. In this paper, we introduce a combinatorial analog of Tutte’s barycentric method, in the plane and on surfaces, leading to a purely discrete algorithm. A first motivation comes from the instability of embeddings under small perturbations. Even in the plane, the resolution of Tutte embeddings (the maximum distance between two vertices, or between a vertex and a non-incident edge, assuming the minimum edge length is at least one) can be exponential in the number of vertices of the graph [ 10 , 8 ] , so rounding may easily create crossings. The situation is worse on surfaces. On piecewise-linear surfaces, computing shortest paths exactly requires exact arithmetic to compare sums of square roots, which is not known to be doable in polynomial time [ 13 ] . Obviously, the situation is even worse on smooth surfaces of negative curvature, e.g., hyperbolic surfaces. A second motivation comes from the existing applications of Tutte’s theorem to morphing. In this setting, one cannot expect closed-form descriptions of the morph. In contrast, in a discrete world, one builds a sequence of local moves from an embedding to the other, in which each intermediate step is an embedding, thus computing a “discrete isotopy” between two given embeddings. Our result is a first step towards building such a sequence in which the edge lengths do not vary too much. More generally, when devising algorithms for topological problems on surfaces, one often faces the following challenge. On the one hand, these problems are, in principle, easily solved by endowing the surface with a metric of negative curvature, which then enjoys useful properties (this is not possible for sporadic surfaces such as the sphere or the torus, but those can usually be dealt with separately). On the other hand, such smooth surfaces are not suitable for discrete algorithms. One thus has to design discrete models that retain the nice properties of smooth surfaces as much as possible. Such a discretization generally takes the following form: one considers a fixed “host” graph (cellularly) embedded on a surface S , and restricts all curves to lie in that graph. The properties of the host graph, and the definition of a