We establish new upper bounds on the number of Euclidean embeddings, up to rigid transformations, of generically minimally rigid graphs with fixed edge lengths, in real, complex and spherical space. These are the first bounds that significantly improve upon Bezout's root count on the corresponding algebraic system. For instance, it is shown that Laman graphs admit less than 3.78^n embeddings (conjectured to be less than 3.5^n), where the exponent n stands for the number of graph vertices, while the previous bound was 4^n. Note that there remains a gap with lower bounds; for Laman graphs, this is about 2.5^n. Unlike previous approaches that relied on algebraic geometry, our methods primarily leverage graph theoretic techniques, including graph orientations, and a process of edge elimination.

This is joint work with Evangelos Bartzos and Raimundas Vidunas.