2025/08/18 by David Garber, Chaya Keller, Garber, David +5
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2508.12789
openalex publication_date 2025/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 n\choose2-(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 > n0 and any g(n)≤ t ≤ n\choose2-(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 n\choose2-(n-1), which is 1 less than the maximum.