Introduction
The "embedding problem" asks how many ways a rigid framework—a set of vertices connected by fixed-length edges—can be realized in Euclidean space. This problem is central to fields like robotics, where it determines the number of configurations for a robot arm, and bioinformatics, where it relates to the possible shapes of protein molecules. While a framework might be rigid (incapable of continuous deformation), it can often exist in multiple discrete "modes" or embeddings. Determining the maximum number of these embeddings for a graph with $n$ vertices remains a significant challenge in distance geometry.
Algebraic Reformulation and Mixed Volume
Traditional approaches to counting embeddings often rely on systems of quadratic distance equations: $(x_i - x_j)^2 + (y_i - y_j)^2 = l_{ij}^2$. However, solving these directly is computationally expensive and often yields "solutions at infinity" that artificially inflate upper bounds.
This paper introduces a more efficient algebraic formulation. By introducing a new variable $w_i = x_i^2 + y_i^2 + z_i^2$, the authors "clean up" the polynomial system, reducing the number of extraneous solutions. To estimate the number of valid embeddings, they employ Mixed Volume (Bernstein’s Bound). Unlike the standard Bézout bound, Mixed Volume accounts for the sparsity of the equations—the fact that most variables do not interact with each other—providing much tighter upper bounds on the number of complex solutions.
Inductive Graph Construction
To systematically study rigid graphs, the authors utilize Henneberg sequences, which build complex rigid structures by adding one vertex at a time according to specific rules. In 2D, these are Laman graphs; in 3D, they correspond to the 1-skeleta of simplicial polyhedra.
As shown in the figure above, the simplest step ($H_1$) involves adding a vertex connected to two existing vertices in 2D or three in 3D. This step predictably doubles the number of embeddings. The complexity arises from $H_2$ and $H_3$ steps, which involve more intricate edge reassignments and are the primary source of the "gaps" in current mathematical bounds.
Key Results and Improved Bounds
Using a custom SAGE-based tool, the authors analyzed over 20,000 graphs and 40,000 polynomial systems. Their work established a new record-breaking lower bound for 3D spatial embeddings: $16^{\lfloor(n-3)/3\rfloor} \approx 2.52^n$, derived from a "caterpillar" construction of cyclohexane-like units.
For small $n$, the authors significantly narrowed the range between known minimum and maximum embeddings. As seen in Table 1, they improved the 2D upper bound for $n=10$ to 2048. In 3D, they established tight bounds for graphs with up to 7 vertices, proving, for instance, that the cyclohexane graph ($n=6$) has exactly 16 embeddings.
Conclusion
While this research provides the tightest bounds to date for small rigid graphs, challenges remain. The Mixed Volume counts solutions in the complex domain, whereas physical embeddings must be real. Consequently, the derived upper bounds may still exceed the true physical maximum. Future work will focus on bridging this gap between real and complex roots and developing a complete combinatorial characterization for 3D rigidity.
Summary updated