Journal article
Playing with Triangulations
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.
Authors
Aichholzer O; Bremner D; Demaine ED; Hurtado F; Kranakis E; Krasser H; Ramaswami S; Sethia S; Urrutia J
Journal
Lecture Notes in Computer Science, Vol. 2866, , pp. 22–37
Publisher
Springer Nature
Publication Date
2003
DOI
10.1007/978-3-540-44400-8_4
ISSN
0302-9743