An Inductive Construction for Plane Laman Graphs via Vertex Splitting

We prove that all planar Laman graphs (i.e. minimally generically rigid graphs with a non-crossing planar embedding) can be generated from a single edge by a sequence of vertex splits. It has been shown recently [6,12] that a graph has a pointed pseudo-triangular embedding if and only if it is a planar Laman graph. Due to this connection, our result gives a new tool for attacking problems in the area of pseudo-triangulations and related geometric objects. One advantage of vertex splitting over alternate constructions, such as edge-splitting, is that vertex splitting is geometrically more local.We also give new inductive constructions for duals of planar Laman graphs and for planar generically rigid graphs containing a unique rigidity circuit. Our constructions can be found in O(n3) time, which matches the best running time bound that has been achieved for other inductive contructions.