Emanation graph: a plane geometric spanner with Steiner points
From MaRDI portal
Publication:2698543
DOI10.1007/s00373-023-02632-0OpenAlexW3160796411MaRDI QIDQ2698543
Bardia Hamedmohseni, Zahed Rahmati, Debajyoti Mondal
Publication date: 24 April 2023
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.10376
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- On plane geometric spanners: a survey and open problems
- Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations
- Delaunay graphs are almost as good as complete graphs
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- Constructing plane spanners of bounded degree and low weight
- Improved bounds on the spanning ratio of the theta-5-graph
- Towards tight bounds on theta-graphs: more is not always better
- Classes of graphs which approximate the complete Euclidean graph
- Construction and local routing for angle-monotone graphs
- Improved spanning ratio for low degree plane spanners
- Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions
- There are planar graphs almost as good as the complete graph
- The \(\varTheta_5\)-graph is a spanner
- There are plane spanners of degree 4 and moderate stretch factor
- Improved bounds on the stretch factor of \(Y_{4}\)
- On the Stretch Factor of the Theta-4 Graph
- The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
- GraphMaps: Browsing Large Graphs as Interactive Maps
- Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition
- New and improved spanning ratios for Yao graphs
- Degree four plane spanners: Simpler and better
- Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
- YAO GRAPHS SPAN THETA GRAPHS
- Simplified Emanation Graphs: A Sparse Plane Spanner with Steiner Points
- Plane Spanners of Maximum Degree Six
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Planar spanners and approximate shortest path queries among obstacles in the plane
- π/2-ANGLE YAO GRAPHS ARE SPANNERS
- A Faster Algorithm for Computing Straight Skeletons
- Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints
- On the Spanning and Routing Ratio of Theta-Four
- Graph Drawing
- Lower Bounds on the Dilation of Plane Spanners
- Increasing-Chord Graphs On Point Sets