  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.
