View PDF HTML (experimental)

Abstract:The set of triangulations of a surface $\Sigma$ with a prescribed set $X$ of vertices can be endowed with a graph structure $\mathcal{F}(\Sigma,X)$ called a flip-graph, whose edges connect two triangulations that differ by a single arc. It is known that when $X$ is the vertex set of a convex Euclidean polygon $\mathrm{P}$, the subgraph $\mathcal{F}_\varepsilon(\mathrm{P},X)$ induced in $\mathcal{F}(\mathrm{P},X)$ by the triangulations that contain a given arc $\varepsilon$ is strongly convex in the sense that all the geodesic paths in $\mathcal{F}(\mathrm{P},X)$ between two such triangulations remain in that subgraph. Here, we provide a related result that involves a triangle instead of an arc: we show that if the three edges of a triangle $\tau$ appear in (possibly distinct) triangulations along a geodesic path in $\mathcal{F}(\mathrm{P},X)$, then $\tau$ must belong to a triangulation in that path. More generally, we prove that certain $3$\nobreakdash-dimensional simplicial complexes related to the geodesics in $\mathcal{F}(\mathrm{P},X)$ are flag and provide two consequences. The first consequence is that $\mathcal{F}_\varepsilon(\mathrm{P},X)$ is not always strongly convex when $X$ is obtained from the vertex set of $P$ by adding just two points. The second, in the case when $\Sigma$ is a topological surface, is that the number of arc crossings between two triangulations does not allow to approximate their distance in $\mathcal{F}(\Sigma,X)$ by a factor of less than $3/2$.

Submission history

From: Lionel Pournin [view email]
[v1] Tue, 15 Jun 2021 09:46:13 UTC (2,974 KB)
[v2] Mon, 13 Sep 2021 16:58:14 UTC (832 KB)
[v3] Tue, 1 Sep 2026 13:50:23 UTC (882 KB)