On saturated (maximal-for-inclusion) 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. Such a graph 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 \choose 2}-(n-2). 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; i.e., they are maximal with respect to inclusion.

In settings that the extremal size is close to {n \choose 2}, it is more convenient to pass to the complementary graph and to consider blockers, which are sets of edges which intersect each triangulation. Clearly, the minimal size of a blocker for triangulation is n-2. A blocker is called saturated (or minimal-for-inclusion) if the deletion of any of its edges will transform it into a non-blocker.

In the talk, we use the simpler language of blockers, and we present our two main results, and a sketch of their proofs:
1. The possible sizes of saturated blockers.
2. The complete characterization of saturated blockers of size n-1.

Joint work with Chaya Keller (Ariel), Olga Nissenbaum (Ariel) and Shimon Aviram (HIT).