An asymptotic upper bound for graph embeddings

We address a central question in rigidity theory, namely to bound the number of Euclidean or spherical embeddings of minimally rigid graphs. Since these embeddings correspond to the real roots of certain algebraic systems, the same enumerative question can be asked in complex spaces. Bezout's bound on the quadratic equations that capture the edge lengths yields trivially a bound of O(2dmiddot|V|) embeddings, for graphs of |V| vertices in d dimensions; it had not been improved until recently. A first improvement was obtained for d > 5 (Bartzos et al., 2020). The same work related the number of embeddings and the number of a class of graph orientations. A combinatorial analysis based on the latter yielded the first nontrivial upper bounds for 2 < d < 4, while further improving the bounds for d > 5 (Bartzos et al., 2022).Here, we follow a similar procedure as in Bartzos et al. (2022). First we obtain upper bounds on graph orientations with fixed outdegree by enhancing the existing graph theoretic tools. Then we use the relation between graph orientations and the bound on the embedding number to provide new upper bounds in all dimensions on the number of complex embeddings by extending the recent progress. Namely, for d = 2 (Laman graph embeddings) and d = 3, we improve the upper bound from O(3.78|V|) to O(3.46|V|) and from O(6.84|V|) to O(6.32|V|), respectively.Regarding the tightness of our results, we present examples of graphs indicating that our bound on the outdegree-constrained orientations may be sharp, but we have no similar data for the embedding number.(c) 2022 Elsevier B.V. All rights reserved.