A deterministic linear time algorithm for geometric separators and its applications

David Eppstein, Gary L. Miller, and Shang-Hua Teng
Fundamenta Informaticae 22(4):309–331, Apr 1995
Proc. 9th Symp. Computational Geometry, ACM, May 1993, pp. 99–108
Mathematical Reviews 96m:68162
http://www.acm.org/pubs/citations/proceedings/compgeom/160985/p99-eppstein/
http://www.ics.uci.edu/~eppstein/pubs/EppMilTen-FI-95.ps.gz

Cited by:

• Moments of inertia and graph separators
• A unified approach to approximation problems for NP- and PSPACE-hard problems for geometric graphs
• An approximation scheme for planar graph TSP
• Automatic mesh partitioning
• Disk packings and planar separators
• Derandomization in computational geometry
• Approximation algorithms for maximum two-dimensional pattern matching
• Prepartitioning as a way to mesh subdomains in parallel
• Separators for sphere-packings and nearest neighbor graphs
• Automatic partitioning techniques for solving partial differential equations on irregular adaptive meshes
• Geometric separators for finite-element meshes
• A divide-and-conquer algorithm for min-cost perfect matching in the plane
• Combinatorial aspects of geometric graphs
• Data generation for geometric algorithms on non-uniform distributions
• Well-separated pair decomposition for the unit-disk graph metric and its applications
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• New Results on Combinatorial Algorithms
• Multi-way Graph and Hypergraph Partitioning