Density Graphs and Separators
Gary Lee Miller, Stephen A. Vavasis · eCommons (Cornell University) · 1990
We propose a class of graphs that would occur naturally in finite-element problems, and we prove a bound on separators for this class of graphs. For three-dimensional graphs, our separator bound is $O(N^{2/3})$. We also propose a simple randomized algorithm to find this separator in $O(N)$ time. Such an algorithm would be used as a preprocessing step for the domain decomposition method of efficiently solving a finite-element problem on a parallel computer. This paper generalizes "local graphs" of Vavasis [1990] to the case of graphs with varying densities of nodes. It also generalizes aspects of Miller and Thurston's [1990] "stable graphs."