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 $F$ be a family of subgraphs of $G$. A blocker for $F$ is a set of edges, of smallest possible size, that contains a common edge with every element of $F$. Previous works determined the blockers for various families $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 $B$ of blockers for the family $T$ of triangulations of $C$. In particular, we show that $|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$. Namely, 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$.

12 pages, 7 figures