Counting realizations of Laman graphs on the sphere (Q2189421)

Generically minimally rigid graphs in the plane (Laman graphs) admit only finitely many realizations in the plane for a generic assignment of edge-lengths. Recently, substantial progress has been made in the computation of the number of non-isometric realizations in the complex extension of the Euclidean plane [\textit{J. Capco} et al., SIAM J. Appl. Algebra Geom. 2, No. 1, 94--125 (2018; Zbl 1439.14182)]. This paper presents a recursive algorithm for computing the number of non-isometric realizations of Laman graphs in the complex sphere (where they are also known to be generically minimally rigid). It differs fundamentally from the algorithm for computing the number of planar realizations presented in the aforementioned article. The basic idea is to view a realization with prescribed edge lengths, up to sphere isometries, as a tuple of points on the complex projective line with prescribed cross-ratios. The compactification of this space is the moduli space of stable rational curves with marked points. Its Chow rings, as described information [\textit{S. Keel}, Trans. Am. Math. Soc. 330, No. 2, 545--574 (1992; Zbl 0768.14002)], play a crucial role in the algorithm for computing the desired number of realizations. Even if detailed timing information is missing, the devised algorithm seems to be substantially faster than naive approaches via Gröbner bases. It allows a systematic exploration for Laman graphs of low vertex numbers. An interesting observation is that the graphs with a maximal number of realizations need not be the same for the planar and the spherical version of the problem.