3 papers
cs.CG2026
A Discrete Analog of Tutte's Barycentric Embeddings on Surfaces
Ãric Colin de Verdière, Vincent Despré, Loïc Dubois
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 vertice…
cs.CG2026
Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface
Loïc Dubois
Every surface that is intrinsically polyhedral can be represented by a portalgon: a collection of polygons in the Euclidean plane with some pairs of equally long edges abstractly i…
cs.CG2025
Untangling Graphs on Surfaces
Ãric Colin de Verdière, Vincent Despré, Loïc Dubois
Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle points), possibly with crossings. We provide an algorithm to decide whether such a drawin…