Theory Group Meeting

ABSTRACT:  Given a graph, one can embed its vertices in space and view its edges as solid bars joined at vertices. If this obtained framework is rigid, i.e., its shape cannot be modified, then the graph is called rigid. The algorithmic questions here are to test if a given graph is rigid and if yes,  construct a rigid embedding. The answer depends on the dimension of the underlying space. The problem has a randomized polynomial time algorithm via the Polynomial Identity Testing (PIT) algorithm (for every dimension). For dimension 2, there is also a deterministic algorithm, which is combinatorial. We want to derandomize the algorithm based on PIT.