Geometry and generation of a new graph planarity game

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

doi:10.7155/jgaa.00504

Geometry and generation of a new graph planarity game

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

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

99 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 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	https://doi.org/10.7155/jgaa.00504
Publication status	Published - 2019

Access to Document

10.7155/jgaa.00504

published versionFinal published version, 911 KB

Cite this

@article{c9c1d09eb91d4152a0d72a69574f218b,

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

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

year = "2019",

doi = "10.7155/jgaa.00504",

language = "English",

volume = "23",

pages = "603--624",

journal = "Journal of Graph Algorithms and Applications",

issn = "1526-1719",

publisher = "Brown University",

number = "4",

}

TY - JOUR

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 - 2019

Y1 - 2019

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

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

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

U2 - 10.7155/jgaa.00504

DO - 10.7155/jgaa.00504

M3 - Article

SN - 1526-1719

VL - 23

SP - 603

EP - 624

JO - Journal of Graph Algorithms and Applications

JF - Journal of Graph Algorithms and Applications

IS - 4

ER -

Geometry and generation of a new graph planarity game

Abstract

Access to Document

Other files and links

Fingerprint

Cite this