# Rigidity, Circuits and Combinatorial Resultants

## Ileana Streinu, Smith College

## Date and time: 2pm (New York time), Tuesday, April 13, 2021

## Place: On Zoom (details provided on the seminar mailing list)

Given a graph together with positive weights associated to its edges,
the “2D Localization” problem asks for a placement of the graph
vertices in the plane such that the edge lengths match the given
weights. A slightly easier case — the “single unknown distance”
problem — asks only for the possible values of one unknown distance
between a pair of vertices. Both problems can be easily formulated
algebraically and could, in principle, be addressed with variations of
the doubly-exponential time Groebner Basis algorithm. But of course
this is not feasible in practice, even for small cases.

Known results from rigidity theory, together with techniques involving
algebraic matroids, a theorem of Lovasz and Dress and the formulation
of the problem in terms of Cayley (rather than Cartesian) coordinates,
help reduce the single-distance problem to the computation of a
so-called circuit polynomial in the Cayley-Menger ideal.

By taking into account combinatorial rigidity properties of the
underlying graphs, we develop a new algorithm that significantly
outperforms Groebner Bases for computing such polynomials. We
introduce a new operation on graphs called a “combinatorial
resultant,” which captures properties of the Sylvester resultant of
two polynomials in the algebraic rigidity matroid. We show that every
rigidity-circuit graph has a “construction tree,” with this operation
marking the tree's interior nodes and with K4 graphs at the
leaves. Our algorithm performs an algebraic elimination (using
classical resultants) guided by the construction tree. A number of
intriguing open questions remain — both combinatorial and algebraic.

To demonstrate the effectiveness of our new method, we implemented it
in Mathematica: it took less than 15 seconds on an example where a
Groebner Basis calculation took 5 days and 6 hrs.

This is joint work with Goran Malic.