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( n3/2 ) bound is achieved on the nullspace basis size (i.e., the number of nonzero entries in the basis), and O( nlog n ) an bound on the size in the special case of grid graphs.