Geometry and generation of a new graph planarity game

DOI10.7155/JGAA.00504zbMATH Open1419.05139arXiv1908.01426OpenAlexW2972582358MaRDI QIDQ5233138FDOQ5233138

Authors: Rutger Kraaijer, Wouter Meulemans, André van Renssen, Marc Van Kreveld 

Publication date: 16 September 2019

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1908.01426

Recommendations

• Drawing arrangement graphs in small grids, or how to play Planarity
• Drawing arrangement graphs in small grids, or how to play planarity
• Untangling a Planar Graph
• Moving Vertices to Make Drawings Plane
• On the obfuscation complexity of planar graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• A linear algorithm for embedding planar graphs using PQ-trees
• Minimum-weight triangulation is NP-hard
• Computational geometry. Algorithms and applications.
• On the number of plane geometric graphs
• How to draw a planar graph on a grid
• Untangling a planar graph
• Handbook of graph drawing and visualization
• Semispaces of configurations, cell complexes of arrangements
• On embedding an outer-planar graph in a point set
• Enumerating order types for small point sets with applications
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• A polynomial bound for untangling geometric planar graphs
• On the obfuscation complexity of planar graphs
• Every graph admits an unambiguous bold drawing
• Bold graph drawings
• Swapping labeled tokens on graphs

Cited In (4)

• Localization game on geometric and planar graphs
• Ruler of the plane -- games of geometry
• The region smoothing swap game
• Untangling circular drawings: algorithms and complexity

Uses Software

• NetLogo

This page was built for publication: Geometry and generation of a new graph planarity game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5233138)