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 graphfast distance queriesintersection graphsparse spanners

Mathematics Subject Classification ID

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

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

(15)

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

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)