Spanners for Geometric Intersection Graphs

Details Spanners for Geometric Intersection Graphs Spanners for Geometric Intersection Graphs

2006-05-07

arxiv.org/abs/cs/0605029v1

Computer Science

Computational Geometry

16 pages, 5 figures, Latex

Scientific paper

Efficient algorithms are presented for constructing spanners in geometric intersection graphs. For a unit ball graph in R^k, a (1+\epsilon)-spanner is obtained using efficient partitioning of the space into hypercubes and solving bichromatic closest pair problems. The spanner construction has almost equivalent complexity to the construction of Euclidean minimum spanning trees. The results are extended to arbitrary ball graphs with a sub-quadratic running time. For unit ball graphs, the spanners have a small separator decomposition which can be used to obtain efficient algorithms for approximating proximity problems like diameter and distance queries. The results on compressed quadtrees, geometric graph separators, and diameter approximation might be of independent interest.

Affiliated with

Also associated with

No associations

Rating

Spanners for Geometric Intersection Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spanners for Geometric Intersection Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spanners for Geometric Intersection Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463353