Abstract
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.
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 language | English |
|---|---|
| Pages (from-to) | 603-624 |
| Number of pages | 22 |
| Journal | Journal of Graph Algorithms and Applications |
| Volume | 23 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2019 |