Rectangular spiral galaxies are still hard
From MaRDI portal
Publication:2678258
DOI10.1016/j.comgeo.2022.101949zbMath1506.05139arXiv2110.00058MaRDI QIDQ2678258
Erik D. Demaine, Maarten Löffler, Christiane Schmidt
Publication date: 9 January 2023
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2110.00058
91A43: Games involving graphs
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05B50: Polyominoes
05C57: Games on graphs (graph-theoretic aspects)
Cites Work
- Unnamed Item
- A better heuristic for orthogonal graph drawings
- Towards an algorithmic guide to Spiral Galaxies
- Height-Preserving Transformations of Planar Graph Drawings
- 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
- Minimum-weight triangulation is NP-hard
- Planar 3DM is NP-complete
- The Complexity of Planar Counting Problems