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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

1 Citaat (Scopus)

7 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Titel	Proceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)
Plaats van productie	Piscataway
Uitgeverij	Institute of Electrical and Electronics Engineers
Aantal pagina's	8
ISBN van elektronische versie	978-1-5386-4359-4
DOI's	https://doi.org/10.1109/CIG.2018.8490404
Status	Gepubliceerd - 2018
Evenement	2018 IEEE Conference on Computational Intelligence and Games (CIG) - Maastricht, Netherlands, Maastricht, Nederland Duur: 14 aug. 2018 → 17 aug. 2018

Congres

Congres	2018 IEEE Conference on Computational Intelligence and Games (CIG)
Land/Regio	Nederland
Stad	Maastricht
Periode	14/08/18 → 17/08/18

Toegang tot document

10.1109/CIG.2018.8490404

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@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, Nederland, 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.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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

Samenvatting

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit