Playing with Triangulations

Aichholzer, Oswin; Bremner, David; Demaine, Erik D.; Hurtado, Ferran; Kranakis, Evangelos; Krasser, Hannes; Ramaswami, Suneeta; Sethia, Saurabh; Urrutia, Jorge

Aichholzer, O. (Oswin), Bremner, D. (David), Demaine, E.D. (Erik D.), Hurtado, F. (Ferran), E. Kranakis (Evangelos), Krasser, H. (Hannes), Ramaswami, S. (Suneeta), Sethia, S. (Saurabh) and Urrutia, J. (Jorge)

2003-12-01

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

Additional Metadata
Organisation	School of Computer Science
Citation APA Style AAA Style APA Style Cell Style Chicago Style Harvard Style IEEE Style MLA Style Nature Style Vancouver Style American-Institute-of-Physics Style Council-of-Science-Editors Style BibTex Format Endnote Format RIS Format CSL Format DOIs only Format	Aichholzer, O. (Oswin), Bremner, D. (David), Demaine, E.D. (Erik D.), Hurtado, F. (Ferran), Kranakis, E, Krasser, H. (Hannes), … Urrutia, J. (Jorge). (2003). Playing with Triangulations.

Playing with Triangulations

Publication

Publication

Playing with Triangulations

Publication

Publication

Workflow

Workflow

Add Content