2026-07-22T01:37:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25538 2026-03-19T13:34:41Z ddc:004 open_access

2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs Gurjar, Rohit Rothmund, Kilian Thierauf, Thomas Graph Rigidity Parallel Algorithms Polynomial Identity Testing Derandomization Minimally rigid graphs can be decided and embedded in the plane efficiently, i.e. in polynomial time. There is also an efficient randomized parallel algorithm, i.e. in RNC. We present an NC-algorithm to decide whether one-crossing-minor-free graphs are minimally rigid. In the special case of K_{3,3}-free graphs, we also compute an infinitesimally rigid embedding in NC. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Gurjar and Kilian Rothmund and Thomas Thierauf 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.49 urn:nbn:de:0030-drops-255385 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.49 eng https://creativecommons.org/licenses/by/4.0/legalcode