Games on Triangulations [Dagstuhl version]

Abstract. 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 speci¯c 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 ¯nd a winning strategy. Along the way, we show connections to existing combinatorial games such as Kayles and Nimstring (a variation on Dots-and-Boxes).