Applications of a poset representation to edge connectivity and graph rigidity

A poset representation for a family of sets defined by a labeling algorithm is investigated. Poset representations are given for the family of minimum cuts of a graph, and it is shown how to compute them quickly. The representations are the starting point for algorithms that increase the edge connectivity of a graph, from λ to a given target τ=λ+δ, adding the fewest edges possible. For undirected graphs the time bound is essentially the best-known bound to test τ-edge connectivity; for directed graphs the time bound is roughly a factor δ more. Also constructed are poset representations for the family of rigid subgraphs of a graph, when graphs model structures constructed from rigid bars. The link between these problems is that they all deal with graphic matroids