On Spanners of Geometric Graphs

DOI10.1007/978-3-642-02017-9_8MaRDI QIDQ3630189zbMATH OpenOpenAlexFDO

Authors Iyad Kanj

Publication date 3 June 2009

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

Full work available at URL https://doi.org/10.1007/978-3-642-02017-9_8

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On spanners and lightweight spanners of geometric graphs
• On geometric spanners of Euclidean and unit disk graphs
• Computing Lightweight Spanners Locally
• There are plane spanners of degree 4 and moderate stretch factor
• scientific article; zbMATH DE number 1263225

Cited in

(20)

• Geometric spanners in the MapReduce model
• A lower bound for computing geometric spanners
• Lower bound for sparse Euclidean spanners
• On Pairwise Spanners
• Spanners for geometric intersection graphs with applications
• On spanners and lightweight spanners of geometric graphs
• Simplified emanation graphs: a sparse plane spanner with Steiner points
• Computing Lightweight Spanners Locally
• On plane geometric spanners: a survey and open problems
• Spanners for Geometric Intersection Graphs
• ON SPANNERS OF GEOMETRIC GRAPHS
• scientific article; zbMATH DE number 2014449 (Why is no real title available?)
• On geometric spanners of Euclidean and unit disk graphs
• Geometric Spanners with Small Chromatic Number
• Spanners of Complete k-Partite Geometric Graphs
• Spanning triangulations in graphs
• On a family of strong geometric spanners that admit local routing strategies
• Improved local algorithms for spanner construction
• Sparse hop spanners for unit disk graphs
• Geometric spanners with applications in wireless networks

This page was built for publication: On Spanners of Geometric Graphs

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