GEOMETRIC SEPARATORS FOR FINITE-ELEMENT MESHES

We propose a class of graphs that would occur naturally in finite-elem ent and finite-difference problems and we prove a bound on separators for this class of graphs. Graphs in this class are embedded in d-dimen sional space in a certain manner. For d-dimensional graphs our separat or bound is O(n((d-1)/d)), which is the best possible bound. We also p ropose a simple randomized algorithm to find this separator in O(n) ti me. This separator algorithm can be used to partition the mesh among p rocessors of a parallel computer and can also be used for the nested d issection sparse elimination algorithm.