Abstract We consider the effect of symmetry on the rigidity of bar-joint frameworks, spherical frameworks and point-hyperplane frameworks in $${\mathbb {R}}^d$$ R d . In particular, for a graph $$G=(V,E)$$ G = ( V , E ) and a framework (G, p), we show that, under forced or incidental symmetry, infinitesimal rigidity for spherical frameworks with vertices in some subset $$X\subset V$$ X ⊂ V realised on the equator and point-hyperplane frameworks with the vertices in X representing hyperplanes are equivalent. We then show, again under forced or incidental symmetry, that infinitesimal rigidity properties under certain symmetry groups can be paired, or clustered, under inversion on the sphere so that infinitesimal rigidity with a given group is equivalent to infinitesimal rigidity under a paired group. The fundamental basic example is that mirror symmetric rigidity is equivalent to half-turn symmetric rigidity on the 2-sphere. With these results in hand we also deduce some combinatorial consequences for the rigidity of symmetric bar-joint and point-line frameworks.

A rigidity theory is developed for bar-joint frameworks in $\mathbb{R}^{d+1}$ whose vertices are constrained to lie on concentric $d$-spheres with independently variable radii. In particular, combinatorial characterizations are established for the rigidity of generic frameworks for d=1 with an arbitrary number of independently variable radii, and for $d=2$ with at most two variable radii. This includes a characterization of the rigidity or flexibility of uniformly expanding spherical frameworks in $\mathbb{R}^{3}$. Due to the equivalence of the generic rigidity between Euclidean space and spherical space, these results interpolate between rigidity in one and two dimensions and to some extent between rigidity in two and three dimensions. Symmetry-adapted counts for the detection of symmetry-induced continuous flexibility in frameworks on spheres with variable radii are also provided.

A long-standing problem in rigidity theory is to characterize the graphs which are minimally generically rigid in $3$-space. The results of Cauchy, Dehn, and Alexandrov give one important class, the triangulated convex spheres, but there is an ongoing desire for further classes. We provide such a class, along with methods for verifying generic rigidity that can be extended to other classes. These methods are based on a controlled sequence of vertex splits, a graph theoretic operation known to take a minimally generically rigid framework to a new minimally generically rigid framework with one more vertex. One motivation for this is to have well-understood frameworks which can be used to explore mathematical allostery---frameworks in which adding bars at one site causes changes in rigidity at a distant site. This is an initial step in exploring the possibility of mechanical models for an important behavior in proteins.

A significant range of geometric structures whose rigidity has been explored, for both practical and theoretical purposes, are formed by modifying generically isostatic triangulated spheres. In block and hole structures $(\mathcal{P},\boldsymbol{p})$, some edges are removed (to make holes) and others are added (to create rigid subparts called blocks). Previous work noted a combinatorial analogy, in which blocks and holes played equivalent roles—so that they might be interchanged. In this paper, we geometrically connect stresses in such structures $(\mathcal{P},\boldsymbol{p})$ to first-order motions in a swapped structure $(\overline{\mathcal{P}},\boldsymbol{p})$—where holes become blocks and blocks become holes. When the initial structure is geometrically isostatic, this shows that the swapped structure is also geometrically isostatic, giving the strongest possible correspondence. We use an affine presentation of the statics and the motions to make the key underlying correspondences transparent.

In this paper, we provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

We provide a theoretical foundation for the problem of network localization in which some nodes know their locations and other nodes determine their locations by measuring the distances to their neighbors. We construct grounded graphs to model network localization and apply graph rigidity theory to test the conditions for unique localizability and to construct uniquely localizable networks. We further study the computational complexity of network localization and investigate a subclass of grounded graphs where localization can be computed efficiently. We conclude with a discussion of localization in sensor networks where the sensors are placed randomly.

This paper investigates the local uniqueness of designs of m-circles (lines and circles) in the plane up to inversion under a set of angles of intersection as constraints. This local behavior is studied through the Jacobian of the angle measurements in a form analogous to the rigidity matrix for a framework of points with distance constraints. After showing directly that the complete set of angle constraints on v distinct m-circles gives a matrix of rank 3v - 6, we show that the Jacobian is column equivalent by a geometric correspondence to the rigidity matrix for a bar-and-joint framework in Euclidean 3-space. As a corollary, the complexity of the independence of angle constraints on generic plane circles is the complexity of the old unsolved combinatorial problem of generic rigidity in 3-space. This theory is not known to have a polynomial time algorithm for genericindependence that offers a warning about the complexity of general systems of geometric constraints even in the plane. Our correspondence extends to all dimensions. Angle constraints on spheres in 3-space then match the even more complex first-order theory of frameworks in 4-space. This theory is not predicted to have a polynomial time algorithm for generic points.

Pointed pseudo-triangulations are planar minimally rigid graphs embedded in the plane with pointed vertices (incident to an angle larger than p). In this paper we prove that the opposite statement is also true, namely that planar minimally rigid graphs always admit pointed embeddings, even under certain natural topological and combinatorial constraints. The proofs yield efficient embedding algorithms. They also provide---to the best of our knowledge---the first algorithmically effective result on graph embeddings with oriented matroid constraints other than convexity of faces.

Configurations of points in the plane constrained by directions only or by lengths alone lead to equivalent theories known as parallel drawings and infinitesimal rigidity of plane frameworks. We combine these two theories by introducing a new matroid on the edge set of the complete graph with doubled edges to describe the combinatorial properties of direction-length designs.

This paper defines two concepts of rigidity for tensegrity frameworks (frameworks with cables, bars, and struts): prestress stability and second-order rigidity. We demonstrate a hierarchy of rigidity—first-order rigidity implies prestress stability implies second-order rigidity implies rigidity—for any framework. Examples show that none of these implications are reversible, even for bar frameworks. Other examples illustrate how these results can be used to create rigid tensegrity frameworks. This paper also develops a duality for second-order rigidity, leading to a test which combines information on the self stresses and the first-order flexes of a framework to detect second-order rigidity. Using this test, the following conjecture of Roth is proven: a plane tensegrity framework, in which the vertices and bars form a strictly convex polygon with additional cables across the interior, is rigid if and only if it is first-order rigid.

We prove that, after multiplication with a suitable monomial, every homogeneous bracket polynomial of rank r≥3 can be factored into a meet and join expression in the Cayley algebra. The main tool in our construction is an explicit algorithm for rewriting polynomial functions in terms of synthetic constructions in projective geometry. We also discuss applications of Cayley factorization to automated geometry theorem proving.

From the pattern of its rigidity matrix, we show that a k-frame on a graph (or multigraph) has the matroid structure of the union of k copies of the cycle matroid of the graph. This matrix pattern is applied to three central results about the rigidity of frameworks. An immediate corollary of this matroid union is a characterization of rigid bar and body frameworks in n-space (Tay’s Theorem). This is further specialized to characterize the independence and the rigidity of body and hinge structures in n-space (a new theorem). The two-frame, or union of two copies of the graphic matroid, is truncated to produce plane bar and joint frameworks giving a characterization of minimal infinitesimally rigid bar and joint frameworks in the plane (Laman’s Theorem). Finally, these techniques are used to characterize the graphs of infinitesimally rigid frameworks on other surfaces, such as the flat torus, the cylinder, cones, etc., using matroid unions of cycle and bicycle matroids of the graph.

We present two algorithms for pictures of polyhedral scenes. These algorithms have been conjectured (and used for some time), but only now been verified. The combinatorial algorithm, proposed by Sugihara, uses counts on the incidence structure to characterize pictures which are generically the projection of sharp polyhedral scenes of planes and points. The geometric algorithm, described by Clerk Maxwell and rediscovered in the last decade, uses a reciprocal diagram in the plane to characterize pictures of strict oriented polyhedra in space.