The problem of recognizing $(k,l)$-tight graphs is a fundamental problem that has close connections to well studied problems
like graph rigidity. The problem is better understood for planar graphs as compared to general graphs. For example, deterministic
NC-algorithms for the problem are known for planar graphs, but no such ... more >>>

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 ... more >>>