On plane geometric spanners: a survey and open problems
From MaRDI portal
(Redirected from Publication:359741)
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 path-greedy geometric spanners
Cites work
- \(\pi /2\)-angle Xao graphs are spanners
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- An optimal algorithm for approximate nearest neighbor searching fixed dimensions
- Approximating geometric bottleneck shortest paths
- Classes of graphs which approximate the complete Euclidean graph
- Communication-efficient construction of the plane localized Delaunay graph
- Competitive routing in the half-\(\theta_6\)-graph
- Computing a minimum-dilation spanning tree is NP-hard
- Computing Geometric Minimum-Dilation Graphs Is NP-Hard
- Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
- CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
- Constructing plane spanners of bounded degree and low weight
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- Delaunay graphs are almost as good as complete graphs
- EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
- EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
- Fast Greedy Algorithms for Constructing Sparse Geometric Spanners
- Geometric Spanner Networks
- scientific article; zbMATH DE number 4155925 (Why is no real title available?)
- scientific article; zbMATH DE number 5506217 (Why is no real title available?)
- scientific article; zbMATH DE number 1455125 (Why is no real title available?)
- I/O-efficient algorithms for computing planar geometric spanners
- Improved upper bound on the stretch factor of Delaunay triangulations
- Minimum-weight triangulation is NP-hard
- On bounded degree plane strong geometric spanners
- On Generalized Diamond Spanners
- On geometric spanners of Euclidean and unit disk graphs
- On spanners and lightweight spanners of geometric graphs
- On the geometric dilation of closed curves, graphs, and point sets
- On the Spanning Ratio of Gabriel Graphs and beta-Skeletons
- On the Stretch Factor of Convex Delaunay Graphs
- On the stretch factor of Delaunay triangulations of points in convex position
- Planar spanners and approximate shortest path queries among obstacles in the plane
- Plane Spanners of Maximum Degree Six
- Principles of Distributed Systems
- The geometric dilation of finite point sets
- The stretch factor of \(L _{1}\)- and \(L _{ \infty }\)-Delaunay triangulations
- There are planar graphs almost as good as the complete graph
- There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
Cited in
(46)- Constrained generalized Delaunay graphs are plane spanners
- On the stretch factor of randomly embedded random graphs
- Routing among convex polygonal obstacles in the plane
- Routing in polygonal domains
- Plane hop spanners for unit disk graphs: simpler and better
- Bounded-degree spanners in the presence of polygonal obstacle
- An improved upper bound on dilation of regular polygons
- There are plane spanners of degree 4 and moderate stretch factor
- Upper and lower bounds for online routing on Delaunay triangulations
- On path-greedy geometric spanners
- Emanation graph: a plane geometric spanner with Steiner points
- Lattice spanners of low degree
- Lattice spanners of low degree
- Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
- Simplified emanation graphs: a sparse plane spanner with Steiner points
- Upper and lower bounds for online routing on Delaunay triangulations
- On bounded degree plane strong geometric spanners
- On the stretch factor of polygonal chains
- Euclidean Steiner spanners: light and sparse
- On the stretch factor of polygonal chains
- Spanning properties of Yao and -graphs in the presence of constraints
- scientific article; zbMATH DE number 6792401 (Why is no real title available?)
- A note on optimal degree-three spanners of the square lattice
- Lower bounds on the dilation of plane spanners
- Improved stretch factor of Delaunay triangulations of points in convex position
- Drawing graphs as spanners
- Sunflower hard disk graphs
- scientific article; zbMATH DE number 7765415 (Why is no real title available?)
- Social distancing network creation
- Generalized sweeping line spanners
- Edge sparsification for geometric tour problems
- Generalized sweeping line spanners
- Bounded-degree plane geometric spanners in practice
- Red-black spanners for mixed-charging vehicular networks
- Routing among convex polygonal obstacles in the plane
- Constructing red-black spanners for mixed-charging vehicular networks
- Engineering an algorithm for constructing low-stretch geometric graphs with near-greedy average degrees
- Oriented spanners
- The tight spanning ratio of the rectangle Delaunay triangulation
- Computing shortest paths amid non-overlapping weighted disks
- Improved local algorithms for spanner construction
- Light Euclidean Steiner spanners in the plane
- The complexity of geodesic spanners using Steiner points
- Bounded degree spanners of the hypercube
- Sparse hop spanners for unit disk graphs
- Towards tight bounds on theta-graphs: more is not always better
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)
