Geometry and Generation of a New Graph Planarity Game
Vol. 23, no. 4, pp. 603-624, 2019. Regular paper.
Abstract We introduce a new abstract graph game, ${\rm S{\small WAP} P{\small LANARITY}}$, 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.
Submitted: April 2019.
Reviewed: June 2019.
Revised: July 2019.
Accepted: July 2019.
Final: August 2019.
Published: September 2019.
Communicated by Yoshio Okamoto
article (PDF)