2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs
Abstract
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.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)
- Publication date
- 1 January 2026
- Language
- EN