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 describe main broad categories of these games and provide in various situations polynomial-time algorithms to determine who wins a given game under optimal play, and ideally, to find a winning strategy. Relations to relevant existing combinatorial games, such as Kayles, are also shown.

Reference: O. Aichholzer, D. Bremner, E. Demaine, F. Hurtado, E. Kranakis, H. Krasser, S. Ramaswami, S. Sethia, and J. Urrutia. Playing with triangulations. In Proc. Japan Conference on Discrete and Computational Geometry JCDCG 2002, pages 46-54, Tokyo, Japan, 2002.