A unified geometric approach to graph separators

Author

Miller, Gary L. ; Teng, Shang-Hua ; Vavasis, Stephen A.

Author_Institution

Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA

fYear

1991

fDate

1-4 Oct 1991

Firstpage

538

Lastpage

547

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

computational complexity; computational geometry; graph theory; finite element methods; geometric embedding, randomized linear time algorithms; graph separators; k-nearest neighbor graphs; k-overlap graphs; planar graphs; randomized NC algorithms; separator bound; Complexity theory; Computational geometry; Computer science; Finite element methods; Image analysis; Numerical analysis; Particle separators; Partitioning algorithms; Statistical analysis; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on

Conference_Location

San Juan

Print_ISBN

0-8186-2445-0

Type

conf

DOI

10.1109/SFCS.1991.185417

Filename

185417