Abstract: A graph with prescribed edge-lengths is called rigid if it allows no transformations that preserve the edge-lengths other than translations and rotations, and flexible otherwise. Rigid graphs have finitely many realizations as graphs embedded in the Euclidean plane (with vertices as points and edges as straight segments). The motivating problem is the so-called Localization problem which asks to compute all realizations for a given rigid graph. Moreover, the Localization problem can be reduced to a class of graphs called minimally rigid graphs, i.e. those rigid graphs for which the deletion of any edge results with them becoming flexible. This problem can be solved with Grobner basis methods, however such an approach becomes infeasible for graphs with as few as 6 vertices.
We instead consider a related problem, called the single unknown distance problem: given a minimally rigid graph G with prescribed edge-lengths, compute the set of possible lengths of a "non-edge" of G, i.e. the set of distances between a pair of vertices of G that aren't connected by an edge of G. If we can compute these distances for the non-edges of G that together with the edges of G form a trilateration, we can solve the Localization problem for G in linearly many steps. The single-distance problem can also be solved with Grobner basis methods, but again such an approach suffers from the same issues as in the Localization problem. We will present an algorithm for solving the single-distance problem that outperforms Grobner basis methods dramatically - in one instance we reduced a computation that took 5 days with a Grobner basis method to just 15 seconds.
This algorithm exploits the fact that rigid graphs form a matroid, called the rigidity matroid, which can be realized in three ways: as a graphic, a linear, and an algebraic matroid. The bases of this matroid are the minimally rigid graphs, and each of its circuits can be obtained precisely from some minimally rigid graph by converting some "non-edge" into an edge. The algebraic nature of the rigidity matroid puts the circuits into a 1-to-1 correspondence with unique multi-variate polynomials, called the Circuit Polynomials, whose solution sets are exactly the sets of possible distances of non-edges in minimally rigid graphs. Hence the goal is to compute circuit polynomials efficiently, which is a non-trivial task because they can have millions of monomial terms (the largest that we've computed so far has close to 10 million terms). We have achieved that by introducing a new operation on graphs called "the combinatorial resultant" which guides the algebraic computation in a much more efficient manner than any Grobner basis method.
This work is joint with Ileana Streinu.
Bio: Goran Malic is a postdoctoral researcher with Ileana Streinu's LinKaGe Lab at Smith College and UMass Amherst. His current research interests are in rigidity theory, computational algebraic geometry and matroid theory, with an emphasis on algebraic matroids. He received his Ph.D. in Pure Mathematics from the University of Manchester, UK, in 2015 under the supervision of Alexandre Borovik. Before joining LinKaGe Lab he held postdoc positions at the University of Manchester and the Zagreb School of Economics and Management.
The CICS Theory Seminar is free and open to the public. If you are interested in giving a talk, please email Cameron Musco or Rik Sengupta. Note that in addition to being a public lecture series, this is also a one-credit graduate seminar (CompSci 891M) that can be taken repeatedly for credit.