Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.13096 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914379044225024 |
|---|---|
| author | de Verdière, Éric Colin Despré, Vincent Dubois, Loïc |
| author_facet | de Verdière, Éric Colin Despré, Vincent Dubois, Loïc |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13096 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces de Verdière, Éric Colin Despré, Vincent Dubois, Loïc Computational Geometry 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. |
| title | A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2507.13096 |