Separators in two and three dimensions

Abstract

We show that every graph that is the 1-skeleton of a simplicial complex K in 3-dimensions has a separator of size O(c 2/3 + ~), where c is the number of 3-simplexes in K and 0 is the number of 0simplexes on the boundary of K, if every 3-simplex has bounded aspect-ratio. This is natural generalization of the separator results for planar graphs, such as the Lipton and Tarjan planar separator theorem. We also show that a family of separators of size O(c 2/3) exists and is constructible. Using this family of separators we get an O(n 2) time algorithm for solving linear systems that arise from the finite element method. In particular, we solve linear systems in O(n 2) time where the underlying graph is the 1-skeleton of a simplicial complex having bounded aspect-ratio and small boundary. All the constructions work in RNC with a reasonably small number of processors.