A unified geometric approach to graph separators
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 538-547
- https://doi.org/10.1109/sfcs.1991.185417
Abstract
A class of graphs called k-overlap graphs is proposed. Special cases of k-overlap graphs include planar graphs, k-nearest neighbor graphs, and earlier classes of graphs associated with finite element methods. A separator bound is proved for k-overlap graphs embedded in d dimensions. The result unifies several earlier separator results. All the arguments are based on geometric properties of embedding. The separator bounds come with randomized linear-time and randomized NC algorithms. Moreover, the bounds are the best possible up to the leading term.Keywords
This publication has 14 references indexed in Scilit:
- Separators in two and three dimensionsPublished by Association for Computing Machinery (ACM) ,1990
- Sphere Packings, Lattices and GroupsPublished by Springer Nature ,1988
- A parallel algorithm for finding a separator in planar graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- The analysis of a nested dissection algorithmNumerische Mathematik, 1986
- Finding small simple cycle separators for 2-connected planar graphsJournal of Computer and System Sciences, 1986
- An Algorithmic Theory of Numbers, Graphs and ConvexityPublished by Society for Industrial & Applied Mathematics (SIAM) ,1986
- On the Problem of Partitioning Planar GraphsSIAM Journal on Algebraic Discrete Methods, 1982
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- Generalized Nested DissectionSIAM Journal on Numerical Analysis, 1979
- ON CONVEX POLYHEDRA OF FINITE VOLUME IN LOBAČEVSKIĬ SPACEMathematics of the USSR-Sbornik, 1970