Geometry and generation of a new graph planarity game

DOI10.7155/JGAA.00504MaRDI QIDQ5233138zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

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)