Geometric separators for finite-element meshes

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