Nested Dissection for Sparse Nullspace Bases

Abstract

We 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 null basis computations occurring in a variety of settings. We achieve an O(n**3/2) bound on the nullspace basis size and an O(nlogn) bound on the size in the special case of grid graphs.