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

1 Citation (Scopus)

6 Downloads (Pure)

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	Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Number of pages	8
ISBN (Electronic)	978-1-5386-4359-4
DOIs	https://doi.org/10.1109/CIG.2018.8490404
Publication status	Published - 2018
Event	2018 IEEE Conference on Computational Intelligence and Games (CIG) - Maastricht, Netherlands, Maastricht, Netherlands Duration: 14 Aug 2018 → 17 Aug 2018

Conference

Conference	2018 IEEE Conference on Computational Intelligence and Games (CIG)
Country/Territory	Netherlands
City	Maastricht
Period	14/08/18 → 17/08/18

Keywords

Graphs
Instance generation
Planarity
Puzzle complexity
Puzzle games

Access to Document

10.1109/CIG.2018.8490404

Cite this

@inproceedings{c2cb5994fe4a446f903109ab74f1bb61,

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.",

keywords = "Graphs, Instance generation, Planarity, Puzzle complexity, Puzzle games",

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

year = "2018",

doi = "10.1109/CIG.2018.8490404",

language = "English",

booktitle = "Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "2018 IEEE Conference on Computational Intelligence and Games (CIG) ; Conference date: 14-08-2018 Through 17-08-2018",

}

Kraaijer, R, van Kreveld, MJ, Meulemans, W & van Renssen, A 2018, Geometry and generation of a new graph planarity game. in Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)., 8490404, Institute of Electrical and Electronics Engineers, Piscataway, 2018 IEEE Conference on Computational Intelligence and Games (CIG), Maastricht, Netherlands, 14/08/18. https://doi.org/10.1109/CIG.2018.8490404

Geometry and generation of a new graph planarity game. / Kraaijer, Rutger; van Kreveld, Marc J.; Meulemans, Wouter et al.
Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018). Piscataway: Institute of Electrical and Electronics Engineers, 2018. 8490404.

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 - van Kreveld, Marc J.

AU - Meulemans, Wouter

AU - van Renssen, André

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.

KW - Graphs

KW - Instance generation

KW - Planarity

KW - Puzzle complexity

KW - Puzzle games

UR - http://www.scopus.com/inward/record.url?scp=85056896569&partnerID=8YFLogxK

U2 - 10.1109/CIG.2018.8490404

DO - 10.1109/CIG.2018.8490404

M3 - Conference contribution

BT - Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

T2 - 2018 IEEE Conference on Computational Intelligence and Games (CIG)

Y2 - 14 August 2018 through 17 August 2018

ER -

Geometry and generation of a new graph planarity game

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this