Abstract

The authors propose a nested dissection approach to finding a fundamental cycle basis in a planar graph. The cycle basis corresponds to a fundamental null-space basis of the adjacency matrix. This problem is meant to model sparse null-space 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 an O(n log n) bound on the size in the special case of grid graphs.