Spanners for Geometric Intersection Graphs

DOI10.1007/978-3-540-73951-7_28zbMATH Open1209.05241arXivcs/0605029OpenAlexW1494596592MaRDI QIDQ3603536FDOQ3603536

Authors: Shiva Prasad Kasiviswanathan, Martin Fürer 

Publication date: 17 February 2009

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

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.

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

Recommendations

• Spanners for geometric intersection graphs with applications
• scientific article; zbMATH DE number 7781250
• 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

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)

Cited In (13)

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

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)