OFFSET
1,3
COMMENTS
Minimally rigid graphs in the plane (A227117) are also minimally rigid on the sphere.
By c_S(G) we denote the number of (complex) spherical realizations of a minimally rigid graph G, modulo rotations, when the edge lengths of the graph are chosen generically.
In general, this number is larger than the number of real realizations and larger than or equal to the number of realizations in the complex plane (cf. A306420).
Equivalently, c_S(G) is the number of complex solutions of the quadratic polynomial system {x_1 = y_1 = x_2 = 0, y_2 = l(1,2), (x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2 = l(i,j)^2, x_k^2 + y_k^2 + z_k^2 = 1}, for all edges {i,j} and vertices k. We assume w.l.o.g. that there is an edge between the vertices 1 and 2. The quantities l(i,j) describe the (generic) edge "lengths" (they can also be complex numbers).
Note that the number of realizations is often counted modulo reflection additionally. In this case the realization number is half of what is listed here for n>=3.
Graphs that can be constructed only by a sequence of 0-extensions has 2^(n-2). A 0-extension (also called Henneberg moves of type 2) adds a new vertex and connects it with two existing vertices.
A graph achieving the maximal number of spherical realizations on n vertices is not necessarily unique.
LINKS
Jose Capco, Nauty plugin to compute maximal Laman numbers.
Sean Dewar and Georg Grasegger, The number of realisations of a rigid graph in Euclidean and spherical geometries, Algebraic Combinatorics 7(6), 2024, pp. 1615-1645.
Matteo Gallet, Georg Grasegger, Matthias Himmelmann and Jan Legerský, PyRigi -- a general-purpose Python package for the rigidity and flexibility of bar-and-joint frameworks, 2025.
Matteo Gallet, Georg Grasegger and Josef Schicho, Counting realizations of Laman graphs on the sphere, Electronic Journal of Combinatorics 27(2), 2020.
Georg Grasegger, Explorations on the number of realizations of minimally rigid graphs, arXiv:2502.04736 [math.CO], 2025.
Georg Grasegger, RigiComp - A Mathematica package for computational rigidity of graphs, 2022.
Gerard Laman, On Graphs and Rigidity of Planar Skeletal Structures, J. Engineering Mathematics 4(4), 1970, pp. 331-340.
Hilda Pollaczek-Geiringer, Über die Gliederung ebener Fachwerke, Zeitschrift für Angewandte Mathematik und Mechanik 7(1), 1927, pp. 58-72.
PyRigi Developers, Realization Counting, 2025.
Wikipedia, Laman graph
EXAMPLE
The triangle graph generically has two different realizations on the sphere (by reflection).
The unique minimally rigid graph with on vertices admits four different spherical realizations.
The three prism graph has 32 spherical realizations while all other graphs on 6 vertices have only 16 realizations on the sphere.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Georg Grasegger, Sep 25 2025
STATUS
approved