  A classical problem in Distance Geometry, with multiple practical
applications (in molecular structure determination, sensor network localization
etc.) is to find the possible placements of the vertices of a graph with given
edge lengths. For minimally rigid graphs, the double-exponential Gr\"obner
Bases algorithm with an elimination order can be applied, in theory, but it is
impractical even for small instances. By relating the problem to the
computation of circuit polynomials in the Cayley-Menger ideal, we recently
proposed an algebraic-combinatorial approach and an elimination algorithm for
circuit polynomials [23]. It is guided by a tree structure whose leaves
correspond to complete $K_4$ graphs and whose nodes perform algebraic resultant
operations. In this paper we uncover further combinatorial structure in the
Cayley-Menger algebraic matroid that leads to an extension of our algorithm. In
particular, we generalize the combinatorial resultant operation of [23] to take
advantage of the non-circuit generators and irreducible polynomials in the
Cayley-Menger ideal and use them as leaves of the tree guiding the elimination.
Our new method has been implemented in Mathematica and allows previously
unobtainable calculations to be carried out. In particular, the
$K_{3,3}$-plus-one circuit polynomial, with over one million terms in 10
variables and whose calculation crashed after several days with the previous
method of [23], succeeded now in approx. 30 minutes.
