In graph theory, a rigid graph is a graph that has a finite number of embeddings in R^d up to rigid motions, with respect to a set of edge length constraints. An embedding of graph in R^d is an assignment of vertices to points in R^d, which also induces a set of edge lengths that correspond to the distances between the connected vertices. An important class of rigid graphs is the class of minimally rigid graphs. A minimally rigid graph, is a graph that is rigid and has the property that the removal of any edge yields a graph that is not rigid. It is a major open problem to find tight upper bounds on the number of the embeddings in R^d. For a long period, only the trivial bound of O(2^(d |V|)) was known on the number of embeddings, that is derived from the direct application of Bezout's Theorem. In [Bartzos et al, 2020], the bound was improved for d >= 5, using matrix permanents. Recently in [Bartzos et al, 2021], the asymptotic bound was improved in all dimension. In the special case of d = 2, the asymptotic upper bound was improved to O(3.7764^|V|).
It is known that the number of solutions of a well-constrained algebraic system is related to the number of embeddings. In particular, the number of the complex solutions of such an algebraic system extends the notion of real embeddings in the complex space, allowing us to bound the complex solutions, using tools from the complex algebraic geometry.
In this thesis, by counting outdegree-constrained orientations of a graph that are related to the algebraic bounds [Bartzos et al, 2020], we improve the existing upper bounds, for the class of minimally rigid graphs, on the number of embeddings.