  Rigid graph theory is an active area with many open problems, especially
regarding embeddings in $\mathbb{R}^d$ or other manifolds, and tight upper
bounds on their number for a given number of vertices. Our premise is to relate
the number of embeddings to that of solutions of a well-constrained algebraic
system and exploit progress in the latter domain. In particular, the system's
complex solutions naturally extend the notion of real embeddings, thus allowing
us to employ bounds on complex roots.
  We focus on multihomogeneous B{\'e}zout (m-B{\'e}zout) bounds of algebraic
systems since they are fast to compute and rather tight for systems exhibiting
structure as in our case. We introduce two methods to relate such bounds to
combinatorial properties of minimally rigid graphs in $\mathbb{C}^d$ and $S^d$.
The first relates the number of graph orientations to the m-B\'ezout bound,
while the second leverages a matrix permanent formulation. Using these
approaches we improve the best known asymptotic upper bounds for planar graphs
in dimension~3, and all minimally rigid graphs in dimension $d\geq 5$, both in
the Euclidean and spherical case.
  Our computations indicate that m-B\'ezout bounds are tight for embeddings of
planar graphs in $S^2$ and $\mathbb{C}^3$. We exploit Bernstein's second
theorem on the exactness of mixed volume, and relate it to the m-B{\'e}zout
bound by analyzing the associated Newton polytopes. We reduce the number of
checks required to verify exactness by an exponential factor, and conjecture
further that it suffices to check a linear instead of an exponential number of
cases overall.
