On plane geometric spanners: a survey and open problems
From MaRDI portal
Publication:359741
DOI10.1016/J.COMGEO.2013.04.002zbMATH Open1270.05032OpenAlexW2006095056MaRDI QIDQ359741FDOQ359741
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
Recommendations
- On Spanners of Geometric Graphs
- On Spanners of Geometric Graphs
- ON SPANNERS OF GEOMETRIC GRAPHS
- On bounded degree plane strong geometric spanners
- Geodesic spanners on polyhedral surfaces
- Spanners for geometric intersection graphs with applications
- A lower bound for computing geometric spanners
- On plane constrained bounded-degree spanners
- On plane constrained bounded-degree spanners
- On path-greedy geometric spanners
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22)
Cites Work
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Title not available (Why is that?)
- Geometric Spanner Networks
- Minimum-weight triangulation is NP-hard
- There are planar graphs almost as good as the complete graph
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Delaunay graphs are almost as good as complete graphs
- Title not available (Why is that?)
- 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
- 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
- On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
- 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
- Title not available (Why is that?)
- On Generalized Diamond Spanners
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- On bounded degree plane strong geometric spanners
- π/2-ANGLE YAO GRAPHS ARE SPANNERS
- EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
- CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
- Title not available (Why is that?)
- EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
- Improved upper bound on the stretch factor of delaunay triangulations
- Principles of Distributed Systems
- Title not available (Why is that?)
- 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
Cited In (41)
- Sparse hop spanners for unit disk graphs
- There are plane spanners of degree 4 and moderate stretch factor
- On plane constrained bounded-degree spanners
- Routing among convex polygonal obstacles in the plane
- Routing in polygonal domains
- Constrained generalized Delaunay graphs are plane spanners
- Towards tight bounds on theta-graphs: more is not always better
- Bounded-degree spanners in the presence of polygonal obstacle
- Bounded-degree plane geometric spanners in practice
- Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints
- A note on optimal degree-three spanners of the square lattice
- Red-black spanners for mixed-charging vehicular networks
- On path-greedy geometric spanners
- On the Stretch Factor of Polygonal Chains
- Plane hop spanners for unit disk graphs: simpler and better
- Title not available (Why is that?)
- An improved upper bound on dilation of regular polygons
- Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
- Title not available (Why is that?)
- Lattice Spanners of Low Degree
- Sunflower hard disk graphs
- Upper and lower bounds for online routing on Delaunay triangulations
- Lattice spanners of low degree
- Improved local algorithms for spanner construction
- Drawing graphs as spanners
- Title not available (Why is that?)
- Lower Bounds on the Dilation of Plane Spanners
- Upper and Lower Bounds for Online Routing on Delaunay Triangulations
- Improved stretch factor of Delaunay triangulations of points in convex position
- Generalized sweeping line spanners
- Routing among convex polygonal obstacles in the plane
- On the stretch factor of randomly embedded random graphs
- Euclidean Steiner Spanners: Light and Sparse
- Constructing red-black spanners for mixed-charging vehicular networks
- Bounded degree spanners of the hypercube
- Title not available (Why is that?)
- On bounded degree plane strong geometric spanners
- Social distancing network creation
- Generalized sweeping line spanners
- Emanation graph: a plane geometric spanner with Steiner points
- Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points
This page was built for publication: On plane geometric spanners: a survey and open problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q359741)
