How to make a square grid framework with cables rigid
This paper solves the problem of making a bipartite digraph strongly connected by adding the smallest number of new edges that preserve bipartiteness. A result of Baglivo and Graver shows that this corresponds to making a two-dimensional square grid framework with cables rigid by adding the smallest number of new cables. We prove a min-max formula for the smallest number of new edges in the digraph problem and give a corresponding linear-time algorithm. We generalize these results to the problem of making an arbitrary digraph strongly connected by adding the smallest number of new edges, each of which joins vertices in distinct blocks of a given partition of the vertex set.
square grid framework rigidity graph algorithms strong connectivity connectivity augmentation min-max theorems