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 proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

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 languageEnglish
Title of host publicationProceedings of the 2018 IEEE Conference on Computational Intelligence and Games (CIG 2018)
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Number of pages8
ISBN (Electronic)978-1-5386-4359-4
DOIs
Publication statusPublished - 2018
Event2018 IEEE Conference on Computational Intelligence and Games (CIG) - Maastricht, Netherlands
Duration: 14 Aug 201817 Aug 2018

Conference

Conference2018 IEEE Conference on Computational Intelligence and Games (CIG)
CountryNetherlands
CityMaastricht
Period14/08/1817/08/18

Keywords

  • Graphs
  • Instance generation
  • Planarity
  • Puzzle complexity
  • Puzzle games

Fingerprint Dive into the research topics of 'Geometry and generation of a new graph planarity game'. Together they form a unique fingerprint.

Cite this