Lower Bounds on the Dilation of Plane Spanners
From MaRDI portal
Publication:5890968
DOI10.1142/S0218195916500059zbMath1353.68281OpenAlexW2571228349MaRDI QIDQ5890968
Anirban Ghosh, Adrian Dumitrescu
Publication date: 26 October 2016
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218195916500059
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Sparse hop spanners for unit disk graphs, On the plane angle-monotone graphs, Local routing in sparse and lightweight geometric graphs, Emanation graph: a plane geometric spanner with Steiner points, Unnamed Item, Unnamed Item, Bounded-degree spanners in the presence of polygonal obstacle, Lower Bounds on the Dilation of Plane Spanners, Drawing graphs as spanners, Lattice spanners of low degree
Cites Work
- 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\)
- On the geometric dilation of closed curves, graphs, and point sets
- Sparse geometric graphs with small dilation
- A fast algorithm for approximating the detour of a polygonal chain.
- Generating All Triangulations of Plane Graphs
- Degree Four Plane Spanners: Simpler and Better
- Geometric Spanner Networks
- Plane Spanners of Maximum Degree Six
- On Generalized Diamond Spanners
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- NEW SPARSENESS RESULTS ON GRAPH SPANNERS
- EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
- CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
- Upper Bound on Dilation of Triangulations of Cyclic Polygons
