Spanners for Geometric Intersection Graphs

DOI10.1007/978-3-540-73951-7_28MaRDI QIDQ3603536zbMATH OpenOpenAlexFDO

Authors Shiva Prasad Kasiviswanathan, Martin Fürer

Publication date 17 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0605029

zbMATH Keywords

disk graphintersection graphsparse spannersfast distance queries

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: 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.

Recommendations

• Spanners for geometric intersection graphs with applications
• Hop-spanners for geometric intersection graphs
• On Spanners of Geometric Graphs
• On Spanners of Geometric Graphs
• ON SPANNERS OF GEOMETRIC GRAPHS
• Spanners for geodesic graphs and visibility graphs
• On spanners and lightweight spanners of geometric graphs
• Spanners in Sparse Graphs
• Spanners in sparse graphs
• Visualization of geometric spanner algorithms

Cited in

(14)

• Constant-hop spanners for more geometric intersection graphs, with even smaller size
• ON SPANNERS OF GEOMETRIC GRAPHS
• An improved construction for spanners of disks
• Geometric Spanners for Points Inside a Polygonal Domain
• Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs
• Compact and low delay routing labeling scheme for unit disk graphs
• New constructions of SSPDs and their applications
• Sparse hop spanners for unit disk graphs
• Spanners of Complete k-Partite Geometric Graphs
• Triangles and girth in disk graphs and transmission graphs
• Spanners for geometric intersection graphs with applications
• Relaxed spanners for directed disk graphs
• Algorithms and Computation
• Spanners for directed transmission graphs

This page was built for publication: Spanners for Geometric Intersection Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3603536)