Playing with Triangulations

O. Aichholzer, D. Bremner, E. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia

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. 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.

Reference: O. Aichholzer, D. Bremner, E. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia. Playing with triangulations. In Lecture Notes in Computer Science 2866, Japanese Conference, JCDCG 2002, pages 22-37, 2003.