EUVIMEDEUVIMED entdecken
Crossref

A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces

Éric Colin de Verdière, Vincent Despré, Loïc Dubois

TheoretiCS · 03.07.2026 · Volume 5

DOI: 10.46298/theoretics.26.11 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, online erschienen am 03.07.2026. Verfasst von Éric Colin de Verdière und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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. 48 pages. This is the TheoretiCS journal version

Zitieren

APA

Verdière, É. C. D., Despré, V., & Dubois, L. (2026). A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces. TheoretiCS, Volume 5. https://doi.org/10.46298/theoretics.26.11

Vancouver

Verdière ÉCD, Despré V, Dubois L. A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces. TheoretiCS. 2026;Volume 5. doi:10.46298/theoretics.26.11

BibTeX
@article{Verdire2026,
  author = {Verdière, Éric Colin de and Despré, Vincent and Dubois, Loïc},
  title = {A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces},
  journal = {TheoretiCS},
  year = {2026},
  volume = {Volume 5},
  doi = {10.46298/theoretics.26.11}
}
Kostenlos starten →