Geometry and Generation of a New Graph Planarity Game

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

doi:10.1109/CIG.2018.8490404

Geometry and Generation of a New Graph Planarity Game

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 what good levels look like and we show how they can be generated. We also report on experiments that show how well the generation works.

Original language	English
Title of host publication	2018 IEEE Conference on Computational Intelligence and Games, CIG 2018, Maastricht, The Netherlands, August 14-17, 2018
Publisher	IEEE
Pages	1-8
Number of pages	8
DOIs	https://doi.org/10.1109/CIG.2018.8490404
Publication status	Published - 2018

Access to Document

10.1109/CIG.2018.8490404

Geometry_and_Generation_of_a_New_Graph_Planarity_GameFinal published version, 1.25 MBLicence: Taverne

Cite this

@inproceedings{f3cdcae485be4975b69645e9aeafd633,

title = "Geometry and Generation of a New Graph Planarity Game",

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 what good levels look like and we show how they can be generated. We also report on experiments that show how well the generation works.",

author = "Rutger Kraaijer and Kreveld, {Marc J. van} and Wouter Meulemans and Renssen, {Andr{\'e} van}",

year = "2018",

doi = "10.1109/CIG.2018.8490404",

language = "English",

pages = "1--8",

booktitle = "2018 IEEE Conference on Computational Intelligence and Games, CIG 2018, Maastricht, The Netherlands, August 14-17, 2018",

publisher = "IEEE",

address = "United States",

}

Geometry and Generation of a New Graph Planarity Game. / Kraaijer, Rutger; Kreveld, Marc J. van; Meulemans, Wouter et al.
2018 IEEE Conference on Computational Intelligence and Games, CIG 2018, Maastricht, The Netherlands, August 14-17, 2018. IEEE, 2018. p. 1-8.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Geometry and Generation of a New Graph Planarity Game

AU - Kraaijer, Rutger

AU - Kreveld, Marc J. van

AU - Meulemans, Wouter

AU - Renssen, André van

PY - 2018

Y1 - 2018

N2 - 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 what good levels look like and we show how they can be generated. We also report on experiments that show how well the generation works.

AB - 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 what good levels look like and we show how they can be generated. We also report on experiments that show how well the generation works.

U2 - 10.1109/CIG.2018.8490404

DO - 10.1109/CIG.2018.8490404

M3 - Conference contribution

SP - 1

EP - 8

BT - 2018 IEEE Conference on Computational Intelligence and Games, CIG 2018, Maastricht, The Netherlands, August 14-17, 2018

PB - IEEE

ER -

Geometry and Generation of a New Graph Planarity Game

Abstract

Access to Document

Fingerprint

Cite this