How to make a square grid framework with cables rigid

This paper solves the problem of making a bipartite digraph strongly connec ted 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 o f new edges in the digraph problem and give a corresponding linear-time alg orithm. We generalize these results to the problem of making an arbitrary d igraph strongly connected by adding the smallest number of new edges, each of which joins vertices in distinct blocks of a given partition of the vert ex set.