Who needs crossings? Hardness of plane graph rigidity

DOI10.4230/LIPICS.SOCG.2016.3zbMATH Open1387.68175OpenAlexW2482552401MaRDI QIDQ3132834FDOQ3132834

Authors: 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/

Recommendations

• Realizability of graphs and linkages
• Connected rigidity matroids and unique realizations of graphs
• Realization of Simply Connected Polygonal Linkages and Recognition of Unit Disk Contact Trees
• Rigid realizations of graphs with few locations in the plane
• Planar Embeddings of Graphs with Specified Edge Lengths

zbMATH Keywords

computational geometrycomplexity theorylinkagesgraph drawinggraph rigidity theorygraph global rigidity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (14)

• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Testing the planar straight-line realizability of 2-trees with prescribed edge lengths
• Framework for \(\exists\mathbb{R}\)-completeness of two-dimensional packing problems
• The complexity of the Hausdorff distance
• Enumerating Grid Layouts of Graphs
• The Complexity of Drawing a Graph in a Polygonal Region
• A practical algorithm with performance guarantees for the art gallery problem
• Unit-length rectangular drawings of graphs
• Unit-length rectangular drawings of graphs
• Planar straight-line realizations of 2-trees with prescribed edge lengths
• A tight bound for the number of edges of matchstick graphs
• Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
• Realizability of graphs and linkages
• Smoothing the Gap Between NP and ER

This page was built for publication: Who needs crossings? Hardness of plane graph rigidity

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