We analyze several perfect-information combinatorial games played on planar triangulations. We introduce three broad categories of such games: constructing, transforming, and marking triangulations. In various situations, we develop polynomial-time algorithms to determine who wins a given game under optimal play, and to find a winning strategy. Along the way, we show connections to existing combinatorial games such as Kayles.

School of Computer Science

Aichholzer, O. (Oswin), Bremner, D. (David), Demaine, E.D. (Erik D.), Hurtado, F. (Ferran), Kranakis, E, Krasser, H. (Hannes), … Urrutia, J. (Jorge). (2003). Playing with Triangulations.