This research introduces an NC-algorithm to determine minimal rigidity in one-crossing-minor-free graphs, suggesting efficient solutions for certain graph classes.
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 K3,3-free graphs, we also compute an infinitesimally rigid embedding in NC.
No takes yet. Share an insight, caveat, or question.
Gurjar et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: