Moments of inertia and graph separators
Keith Gremban, Gary Lee Miller, Shang‐Hua Teng · 1994
Graphs that arise from the nite element or nite dierence methods often include geometric information such as the coordinates of the nodes of the graph. The geometric separator algorithm of Miller, Teng, Thurston, and Vavasis uses some of the available geometric information to nd small node separators of graphs. The algorithm utilizes a random sampling technique based on the uniform distribution to nd a good separator. We show that sampling from an elliptic distribution based on the inertia matrix of the graph can signicantly improve the quality of the separator. More generally, given a cost function f on the unit d-sphere Ud , we can dene an elliptic distribution based on the second moments of f . The expectation of f with respect to the elliptic distribution is less than or equal to the expectation with respect to the uniform distribution, with equality only in degenerate cases. We also present experimental results that demonstrate the signicant benet gained by use of the ad...