Geodesic
Geometry and Generation of a New Graph Planarity Game
Journal of graph algorithms and applications, Tome 23 (2019) no. 4, pp. 603-624 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

We introduce a new abstract graph game, ${\rm S{\small WAP} P{\small LANARITY}}$, 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.
DOI : 10.7155/jgaa.00504
Keywords: planarity, graphs, puzzle games, puzzle complexity, instance generation 
@article{JGAA_2019_23_4_a0,
     author = {Rutger Kraaijer and Marc van Kreveld and Wouter Meulemans and Andr\'e van Renssen},
     title = {Geometry and {Generation} of a {New} {Graph} {Planarity} {Game}},
     journal = {Journal of graph algorithms and applications},
     pages = {603--624},
     year = {2019},
     volume = {23},
     number = {4},
     doi = {10.7155/jgaa.00504},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00504/}
}
TY  - JOUR
AU  - Rutger Kraaijer
AU  - Marc van Kreveld
AU  - Wouter Meulemans
AU  - André van Renssen
TI  - Geometry and Generation of a New Graph Planarity Game
JO  - Journal of graph algorithms and applications
PY  - 2019
SP  - 603
EP  - 624
VL  - 23
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00504/
DO  - 10.7155/jgaa.00504
LA  - en
ID  - JGAA_2019_23_4_a0
ER  - 
%0 Journal Article
%A Rutger Kraaijer
%A Marc van Kreveld
%A Wouter Meulemans
%A André van Renssen
%T Geometry and Generation of a New Graph Planarity Game
%J Journal of graph algorithms and applications
%D 2019
%P 603-624
%V 23
%N 4
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00504/
%R 10.7155/jgaa.00504
%G en
%F JGAA_2019_23_4_a0
Rutger Kraaijer; Marc van Kreveld; Wouter Meulemans; André van Renssen. Geometry and Generation of a New Graph Planarity Game. Journal of graph algorithms and applications, Tome 23 (2019) no. 4, pp. 603-624. doi: 10.7155/jgaa.00504

Cité par Sources :