Lower Bounds on the Dilation of Plane Spanners

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

zbMATH Keywords

geometric graphstretch factorplane spannervertex dilation

Mathematics Subject Classification ID

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