Algebraic Graph Theory for Sparse Flexibility Matrices

An efficient algorithm is presented for the formation of suboptimal cycle bases of graphs corresponding to sparse cycle adjacency matrices, leading to the formation of highly sparse flexibility matrices. The algorithm presented employs concepts from algebraic graph theory together with a Greedy-type algorithm to select cycles with small overlaps and uses a simple graph-theoretical method for controlling the independence of the selected cycles.