Lower Bounds on the Number of Realizations of Rigid Graphs.

Area of Science:

• Computational geometry
• Graph theory
• Algebraic geometry

Background:

• Computing the number of realizations of minimally rigid graphs is a complex problem.
• Existing algorithms, while fast, still have exponential complexity.
• Rigid graph theory is crucial in various scientific and engineering fields.

Purpose of the Study:

• To establish a new lower bound for the maximal number of realizations of minimally rigid graphs.
• To extend these findings to rigid graphs in three-dimensional space.
• To leverage recent algorithmic advancements and theoretical frameworks.

Main Methods:

• Utilizing a recently published, fast (though exponential) algorithm for planar minimally rigid graphs.
• Combining computational results with graph gluing theory.
• Extending methodologies to three-dimensional rigid graphs.
• Employing extensive Gröbner basis computations.

Main Results:

• A new lower bound is established for the maximal number of complex realizations for graphs based on vertex count.
• The study successfully extends these lower bound derivations to three-dimensional rigid graphs.
• Gröbner basis computations provided crucial data for the 3D analysis.

Conclusions:

• The research offers improved theoretical bounds for the number of realizations of rigid graphs.
• The findings contribute to a deeper understanding of graph rigidity in both 2D and 3D.
• This work bridges computational and theoretical approaches in graph theory.