Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-103 | 16th July 2025 15:56

2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

RSS-Feed




TR25-103
Authors: Rohit Gurjar, Kilian Rothmund, Thomas Thierauf
Publication: 27th July 2025 08:36
Downloads: 97
Keywords: 


Abstract:

Minimally rigid graphs can be recognized 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 NC-algorithms to recognize 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.



ISSN 1433-8092 | Imprint