Games on triangulations

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