A unified geometric approach to graph separators
Published 9 December 2002
Gary L. Miller, Shang‐Hua Teng, Stephen A. Vavasis
Citations166
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A separator bound is proved for k-overlap graphs embedded in d dimensions, which unifies several earlier separator results.
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
Computer Science
American Mathematical MonthlySphere Packings, Lattices and Groups.
3,443 Citations1989H. S. M. Coxeter, J. H. Conway +1 more
Grundlehren der mathematischen WissenschaftenSphere Packings, Lattices and Groups
1,507 Citations1988John H. Conway, N. J. A. Sloane
SIAM Journal on Applied MathematicsA Separator Theorem for Planar Graphs
1,338 Citations1979Richard J. Lipton, Robert E. Tarjan
SIAM Journal on Numerical AnalysisGeneralized Nested Dissection
549 Citations1979Richard J. Lipton, Donald J. Rose +1 more
It is shown that sparse Gaussian elimination is efficient for any class of graphs which have good separator, and conversely that graphs without good separators are not amenable to sparse GaRussian elimination.
Vector models for data-parallel computing
464 Citations1990Guy E. Blelloch
A model of parallelism that extends and formalizes the Data-Parallel model on which the Connection Machine and other supercomputers are based is described, and it is argued that data-parallel models are not only practical and can be applied to a surprisingly wide variety of problems, they are also well suited for very-high-level languages and lead to a concise and clear description of algorithms and their complexity.
American Mathematical Society eBooksGeometry and Topology of Manifolds
367 Citations2005Conference Geometry and Topology of Manifolds 2004 Hamilton, Ontario, Hans Bodén +3 more
Society for Industrial and Applied Mathematics eBooksAn Algorithmic Theory of Numbers, Graphs and Convexity
354 Citations1986László Lovász
How to Round Numbers Preliminaries and some Applications in Combinatorics Cuts and Joins Chromatic Number, Cliques and Perfect Graphs Minimizing a Submodular Function.
Journal of Computer and System SciencesFinding small simple cycle separators for 2-connected planar graphs
252 Citations1986Gary L. Miller
It is shown that every 2-connected triangulated planar graph with n vertices has a simple cycle C of length at most 2√2 · n which separates the interior vertices A from the exterior vertices B such that neither A nor B contain more than 2 3n vertices.
Mathematics of the USSR-SbornikON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
168 Citations1970Евгений Михайлович Андреев
Efficient parallel solution of linear systems
152 Citations1985Victor Y. Pan, John H. Reif
This paper describes parallel algorithms that have good numerical stability and remain efficient as n grows large and describes a quadratically convergent iterative method that gives the inverse of an n × n rational matrix A, the first known polylog time algorithm that is numerically stable.
Mathematics of the USSR-SbornikON CONVEX POLYHEDRA OF FINITE VOLUME IN LOBAČEVSKIĬ SPACE
143 Citations1970Евгений Михайлович Андреев
Numerische MathematikThe analysis of a nested dissection algorithm
115 Citations1986John R. Gilbert, Robert E. Tarjan
The combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm is analyzed, guaranteeing bounds ofO (n logn) on fill andO(n3/2) on operation count for planar graphs, twodimensional finite element graphs, graph of bounded genus, and graphs of bounded degree withn1/2-separators.
SIAM Journal on Algebraic and Discrete MethodsOn the Problem of Partitioning Planar Graphs
99 Citations1982Hristo Djidjev
It is shown that every planar graph can be partitioned into two or more components of roughly equal size by deleting only $O ( \sqrt{n} )$ vertices, and such a partitioning can be found in time.
Separators in two and three dimensions
75 Citations1990Gary L. Miller, William P. Thurston
It is shown 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 + ~), which gets an O(n 2) time algorithm for solving linear systems that arise from the finite element method.
Points, spheres, and separators: a unified geometric approach to graph partitioning
70 Citations1992Shang‐Hua Teng
A unified geometric approach is presented for graph partitioning--a fundamental problem in computer science that has important applications in numerical analysis, VLSI design, computational geometry, complexity theory, and other fields.
A parallel algorithm for finding a separator in planar graphs
52 Citations1987Hillel Gazit, Gary L. Miller
A randomized parallel algorithm for finding a simple cycle separator in a planar graph based on the solution of Lipton and Tarjan for the sequential case which takes O(n) time and combines with the Pan and Reif algorithm to find a BFS of planargraph in time O(log3(n)) using n1.5/log( n) processors.
Journal of Computer and System SciencesTape bounds for time-bounded turing machines
49 Citations1972Michael S. Paterson
Let L be a language recognized by a nondeterministic (single-tape) Turing machine of time complexity T(n)>=n^2, and L is also recognized by an deterministic ( single-tapes) Turing Machine of tape complexity T^1^/^2(n).
SIAM Journal on Scientific and Statistical ComputingAutomatic Domain Partitioning in Three Dimensions
29 Citations1991Stephen A. Vavasis
The problem of automatically decomposing a mesh contained in a three-dimensional domain into p pieces is considered, and a class of graphs that would naturally arise from a finite-element mesh in three dimensions is introduced.
Journal of the American Mathematical SocietyA Separator Theorem for Nonplanar Graphs
28 Citations1990Noga Alon, Paul Seymour +1 more
Elsevier eBooksOn deleting vertices to make a graph of positive genus planar
13 Citations1987Joan P. Hutchinson, Gary L. Miller