Geometry and generation of a new graph planarity game

Rutger Kraaijer, Marc J. van Kreveld, Wouter Meulemans, André van Renssen

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
172 Downloads (Pure)


We introduce a new abstract graph game, Swap Planarity, where the goal is to reach a state without edge intersections and a move consists of swapping the locations of two vertices connected by an edge. We analyze this puzzle game using concepts from graph theory and graph drawing, computational geometry, and complexity. Furthermore, we specify quality criteria for puzzle instances, and describe a method to generate high-quality instances. We also report on experiments that show how well this generation process works.

Original languageEnglish
Pages (from-to)603-624
Number of pages22
JournalJournal of Graph Algorithms and Applications
Issue number4
Publication statusPublished - 2019


Dive into the research topics of 'Geometry and generation of a new graph planarity game'. Together they form a unique fingerprint.

Cite this