Triangulations are rigid. You can do better using pseudotriangles
Triangles are, definitely, among the most used mathematical objects. One of the reasons is that they are simple (actually the smallest polygon). Another very important reason is that they are rigid, which is the property behind the many structures composed by triangles we can see in our daily life.
But, surprisingly enough, triangulations are not the 2D rigid structures with fewest bars. Such structures are the socalled pointed pseudotriangulations.
Pseudotriangles generalize the notion of triangle by allowing its sides to be, instead of a single segment, a polygonal chain with the property of being inner convex. Hence, triangles are just a particular, “straight”, type of pseudotriangles.
Thus, a pseudotriangulation of a point set is a tessellation of its convex hull by pseudotriangles. Further, a pseudotriangulation is said to be pointed if all the vertices are incident to an angle greater than 180 degrees ( for the sweet ones). The following figure shows, for the same set of points, a triangulation (left) and a pointed pseudotriangulation (right).
It is apparent that pointed pseudotriangulations have fewer edges than triangulations. Actually, Streinu ^{1} showed that for points a pseudotriangulation has edges, with being the number of nonpointed vertices. In particular, a pointed pseudotriangulation has edges, while a triangulation has edges, for being the number of hull points of the set (the only pointed ones in a triangulation).
Back to rigidity, and informally speaking, we can say that a structure is rigid if any movement either breaks the structure or moves the structure as a whole. For an example, a triangle is rigid while a pseudotriangle might not be rigid; the following figure (right) shows a movement which neither breaks the pseudotriangle nor moves it as a whole.
Streinu also proved that, nicely enough considering the previous example, pointed pseudotriangulations are rigid. The left picture in the following figure shows that the previous movement now will move the pointed pseudotriangulation as a whole, as any other movement will do. (Remember that we are working in 2D, so that 3D movements are not allowed.) The reader can figure out the same property for the larger pointed pseudotriangulation in the right picture.
This implies that, in order to construct a rigid 2D structure, pointed pseudotriangulations allow to get rid of many bars with respect to triangulations. In particular, as we have seen above, a pointed pseudotriangulation will use only bars, instead of the bars used by a triangulation.
Streinu also proved that pointed pseudotriangulations are, in fact, minimally rigid. That is, removing any edge would destroy the rigidity. This is very close to proving that is the smallest number of bars we can use for a rigid 2D structure… except that we have to make sure that there are no other minimally rigid structures.
This was precisely the result by Haas et al.^{2}. There we proved that, if a structure is minimally rigid, then it has to be a pointed pseudotriangulation. More precisely, if an abstract graph is planar (2D structures have no crossings) and minimally rigid, then it can be geometrically embedded as a pointedpseudotriangulation.
Interestingly enough, abstract graphs being minimally rigid can be characterized in a purely combinatorial way. Just counting vertices and edges! Laman^{3} proved that a graph with vertices is minimally rigid if, and only if, (i) it has edges and (ii) every subgraph with vertices has at most edges.
An equivalent way of characterizing the graphs with this property is, as proved by Tay and Whiteley ^{4}, the Henneberg construction ^{5}:
Start with an edge joining two vertices. At each step, add a new vertex in one of these two ways:

Henneberg I (vertex addition): insert a new vertex and connect it to two old vertices, using two new edges.

Henneberg II (edge splitting): insert a new vertex on an old edge, which gets split into two new edges, and connect the new vertex to a third old vertex, using one new edge.
Our first proof technique, of a local nature, shows that there are geometric placements of the points in this abstract Henneberg which result in an embedding of the minimally rigid planar graph meeting the conditions a pointed pseudotriangulation (pointedness and pseudotriangles as faces).
Our second proof technique, of a global nature, makes use of a directed version of Tutte’s barycentric embedding ^{6}, adapted to produce pointedpseudotriangulations instead of convex faces.
Both proofs yield efficient embedding algorithms and allow to obtain some stronger results, using a combinatorial abstraction of pseudotriangulations. These combinatorial pseudotriangulations are defined as topological plane embeddings of a graph, together with an assignment of angles which mimics the properties of geometric pseudotriangulations.
Using this notion, part of the authors of [2] could further generalize the previous results to general rigidity and pseudotriangulations ^{7}. Actually, we showed that the rigidity of planar graphs can be stratified according to the number of nonpointed vertices in an associated combinatorial pseudotriangulation.
In summary, apart from having other interesting properties, pseudotriangulations provide a missing link between planarity and rigidity in geometric graph theory.
References
 Ileana Streinu. A combinatorial approach to planar noncolliding robot arm motion planning. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (2000), pages 443453. DOI: http://dx.doi.org/10.1109/SFCS.2000.892132 ↩
 Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, and Walter Whiteley. Planar minimally rigid graphs and pseudotriangulations. Computational Geometry: Theory and Applications, 31:12 (2005), pages 3161. DOI: http://dx.doi.org/10.1016/j.comgeo.2004.07.003 ↩
 Gerard Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics 4:4 (1970), pages 331340. DOI: http://dx.doi.org/10.1007/BF01534980 ↩
 TiongSeng Tay and Walter Whiteley. Generating isostatic graphs. Structural Topology 11 (1985), pages 21–68. http://wwwiri.upc.es/people/ros/StructuralTopology/WholeIssues/st11ocr.pdf ↩
 Lebrecht Henneberg. Die graphische Statik der starren Systeme, Leipzig, 1911, Johnson Reprint 1968. https://archive.org/details/diegraphischest00henngoog ↩
 William Thomas Tutte. How to draw a graph. Proceedings of the London Mathematical Society, s313:1 (1963), pages 743767. DOI: http://dx.doi.org/10.1112/plms/s313.1.743 ↩
 David Orden, Francisco Santos, Brigitte Servatius, and Herman Servatius. Combinatorial pseudotriangulations. Discrete Mathematics, 307 (2007), pages 554566. DOI: http://dx.doi.org/10.1016/j.disc.2005.09.045 ↩
2 comments
[…] Source: https://mappingignorance.org/2015/07/27/triangulationsarerigidyoucandobetterusingpseudotrian… […]
This is interesting work! I wonder what a minimally rigid tessellation would look like. Is there some subgraph that I could repeat arbitrarily many times to make a structure and the result would always be a pointed psuedotriangulation, and hence minimally rigid?