An Inductive Construction for Plane Laman Graphs via Vertex Splitting

摘要

We prove that all planar Laman graphs (i.e. minimally gener- ically rigid graphs with a non-crossing planar embedding) can be gener- ated from a single edge by a sequence of vertex splits. It has been shown recently 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(n~3) time, which matches the best running time bound that has been achieved for other inductive contructions.