Nested Dissection for Sparse Nullspace Bases

The authors propose a nested dissection approach to finding a fundamental cycle basis in a planar graph. The cycle basis corresponds to a fundamental nullspace basis of the adjacency matrix. This problem is meant to model sparse nullspace basis computations occurring in a variety of settings. An O (n^3/2) bound is achieved on the nullspace basis size (i. e. , the number of nonzero entries in the basis), and O (n n) an bound on the size in the special case of grid graphs.