Who Needs Crossings? Hardness of Plane Graph Rigidity
From MaRDI portal
Publication:3132834
DOI10.4230/LIPIcs.SoCG.2016.3zbMath1387.68175OpenAlexW2482552401MaRDI QIDQ3132834
Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, Zachary R. Abel
Publication date: 30 January 2018
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/5895/pdf/LIPIcs-SoCG-2016-3.pdf/
computational geometrygraph drawinglinkagescomplexity theorygraph rigidity theorygraph global rigidity
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The Complexity of Drawing a Graph in a Polygonal Region ⋮ Planar straight-line realizations of 2-trees with prescribed edge lengths ⋮ Smoothing the Gap Between NP and ER ⋮ Unit-length rectangular drawings of graphs ⋮ The complexity of the Hausdorff distance ⋮ Enumerating Grid Layouts of Graphs ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
