Lower Bounds on the Dilation of Plane Spanners

DOI10.1007/978-3-319-29221-2_12zbMath1405.68414arXiv1509.07181OpenAlexW2963798875MaRDI QIDQ5890540

Adrian Dumitrescu, Anirban Ghosh

Publication date: 23 March 2016

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.07181

zbMATH Keywords

geometric graphstretch factorplane spanner

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Related Items (3)

An exact algorithm for the minimum dilation triangulation problem ⋮ Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition ⋮ Lattice Spanners of Low Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On plane geometric spanners: a survey and open problems
• 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\)
• Constructing plane spanners of bounded degree and low weight
• On the geometric dilation of closed curves, graphs, and point sets
• Sparse geometric graphs with small dilation
• Computing a minimum-dilation spanning tree is NP-hard
• 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 sparse spanners of weighted graphs
• A fast algorithm for approximating the detour of a polygonal chain.
• There are planar graphs almost as good as the complete graph
• Most finite point sets in the plane have dilation \(>1\)
• There are plane spanners of degree 4 and moderate stretch factor
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• The geometric dilation of finite point sets
• Lattice Spanners of Low Degree
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• Generating All Triangulations of Plane Graphs
• 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
• Lower Bounds on the Dilation of Plane Spanners

This page was built for publication: Lower Bounds on the Dilation of Plane Spanners