On plane geometric spanners: a survey and open problems
From MaRDI portal
Publication:359741
DOI10.1016/j.comgeo.2013.04.002zbMath1270.05032OpenAlexW2006095056MaRDI QIDQ359741
Prosenjit Bose, Michiel H. M. Smid
Publication date: 22 August 2013
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0925772113000357
Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)
Related Items (36)
Constrained generalized Delaunay graphs are plane spanners ⋮ Sparse hop spanners for unit disk graphs ⋮ Euclidean Steiner Spanners: Light and Sparse ⋮ Upper and Lower Bounds for Online Routing on Delaunay Triangulations ⋮ Routing among convex polygonal obstacles in the plane ⋮ Routing in polygonal domains ⋮ Upper and lower bounds for online routing on Delaunay triangulations ⋮ Sunflower hard disk graphs ⋮ On path-greedy geometric spanners ⋮ Social distancing network creation ⋮ Generalized sweeping line spanners ⋮ Generalized sweeping line spanners ⋮ Towards tight bounds on theta-graphs: more is not always better ⋮ Plane hop spanners for unit disk graphs: simpler and better ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ On the stretch factor of randomly embedded random graphs ⋮ Unnamed Item ⋮ On bounded degree plane strong geometric spanners ⋮ Unnamed Item ⋮ Bounded-degree spanners in the presence of polygonal obstacle ⋮ Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points ⋮ On plane constrained bounded-degree spanners ⋮ Improved local algorithms for spanner construction ⋮ Unnamed Item ⋮ Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces ⋮ Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Improved stretch factor of Delaunay triangulations of points in convex position ⋮ Drawing graphs as spanners ⋮ Lattice spanners of low degree ⋮ Bounded degree spanners of the hypercube ⋮ An improved upper bound on dilation of regular polygons ⋮ On the Stretch Factor of Polygonal Chains ⋮ A note on optimal degree-three spanners of the square lattice ⋮ There are plane spanners of degree 4 and moderate stretch factor
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On bounded degree plane strong geometric spanners
- Delaunay graphs are almost as good as complete graphs
- On the stretch factor of Delaunay triangulations of points in convex position
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- Constructing plane spanners of bounded degree and low weight
- On the geometric dilation of closed curves, graphs, and point sets
- I/O-efficient algorithms for computing planar geometric spanners
- Computing a minimum-dilation spanning tree is NP-hard
- Classes of graphs which approximate the complete Euclidean graph
- There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
- On plane constrained bounded-degree spanners
- There are planar graphs almost as good as the complete graph
- Approximating geometric bottleneck shortest paths
- The geometric dilation of finite point sets
- The Stretch Factor of L 1- and L ∞ -Delaunay Triangulations
- Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
- On Spanners and Lightweight Spanners of Geometric Graphs
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
- Geometric Spanner Networks
- Minimum-weight triangulation is NP-hard
- Communication-Efficient Construction of the Plane Localized Delaunay Graph
- Plane Spanners of Maximum Degree Six
- Computing Geometric Minimum-Dilation Graphs Is NP-Hard
- On the Stretch Factor of Convex Delaunay Graphs
- On Generalized Diamond Spanners
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- Planar spanners and approximate shortest path queries among obstacles in the plane
- π/2-ANGLE YAO GRAPHS ARE SPANNERS
- EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
- CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
- EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
- Improved upper bound on the stretch factor of delaunay triangulations
- Principles of Distributed Systems
This page was built for publication: On plane geometric spanners: a survey and open problems
