On saturated triangulation-free convex geometric graphs

A convex geometric graph is a graph whose vertices are the corners of a convex polygon P in the plane and whose edges are boundary edges and diagonals of the polygon. It is called triangulation-free if its non-boundary edges do not contain the set of diagonals of some triangulation of P. Aichholzer et al. (2010) showed that the maximum number of edges in a triangulation-free convex geometric graph on n vertices is {n2}- (n-2), and subsequently, Keller and Stein (2020) and (independently) Ali et al. (2022) characterized the triangulation-free graphs with this maximum number of edges. We initiate the study of the saturation version of the problem, namely, characterizing the triangulation-free convex geometric graphs which are not of the maximum possible size, but yet the addition of any edge to them results in containing a triangulation. We show that, surprisingly, there exist saturated graphs with only g (n) = O (n log n) edges. Furthermore, we prove that for any n > n₀ and any g (n) t {n2}- (n-2), there exists a saturated graph with n vertices and t edges. In addition, we obtain a complete characterization of all saturated graphs whose number of edges is {n2}- (n-1), which is 1 less than the maximum.