Talk information

Date: Sunday, May 10, 2026
Time: 10:10–11:00
Place: Schreiber 309
Speaker: David Garber (Holon Institute of Technology)
Title: On saturated (maximal-for-inclusion) triangulation-free convex geometric graphs


Abstract:

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.

We show that, surprisingly, there exist saturated (maximal-for-inclusion) graphs with only $g(n)=O(n \log n)$ edges. Furthermore, we prove that, for any $n>n_0$ and any $g(n) \leq t \leq {n \choose 2}-(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 \choose 2}-(n-1)$, which is 1 less than the maximum.

In settings that the extremal size is close to ${n \choose 2}$, it is more convenient to pass to the complement 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, and it is easy to see that a blocker is saturated if and only if its complement is a saturated triangulation-free graph.

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 minimal-for-inclusion blockers.
  2. The complete characterization of minimal-for-inclusion blockers of size $n-1$.

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