Blockers for Triangulations of a Convex Polygon and a Geometric Maker-Breaker Game

Abstract

 Let $G$ be a complete convex geometric graph whose vertex set $P$ forms a convex polygon $C$, and let $\mathcal{F}$ be a family of subgraphs of $G$. A blocker for $\mathcal{F}$ is a set of diagonals of $C$, of smallest possible size, that contains a common edge with every element of $\mathcal{F}$. Previous works determined the blockers for various families $\mathcal{F}$ of non-crossing subgraphs, including the families of all perfect matchings, all spanning trees, all Hamiltonian paths, etc.

In this paper we present a complete characterization of the family $\mathcal{B}$ of blockers for the family $\mathcal{T}$ of triangulations of $C$. In particular, we show that $|\mathcal{B}|=F_{2n-8}$, where $F_k$ is the $k$'th element in the Fibonacci sequence and $n=|P|$.

We use our characterization to obtain a tight result on a geometric Maker-Breaker game in which the board is the set of diagonals  of a convex $n$-gon $C$ and Maker seeks to occupy a triangulation of $C$. We show that in the $(1:1)$ triangulation game, Maker can ensure  a win within $n-3$ moves, and that in the $(1:2)$ triangulation game, Breaker can ensure a win within $n-3$ moves. In particular, the threshold bias for the game is $2$.