Approximating the Stretch Factor of Euclidean Graphs

DOI10.1137/S0097539799361671MaRDI QIDQ4507380zbMATH OpenOpenAlexFDO

Authors Giri Narasimhan, Michiel Smid

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539799361671

zbMATH Keywords

computational geometryspannersapproximate shortest pathswell-separated pairs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Approximating the average stretch factor of geometric graphs
• Approximating the average stretch factor of geometric graphs
• On the stretch factor of convex Delaunay graphs
• On the Stretch Factor of Convex Delaunay Graphs
• scientific article; zbMATH DE number 4070353
• Computing the stretch of an embedded graph
• Stretch and diameter in random geometric graphs
• On the stretch factor of randomly embedded random graphs
• Towards tight approximation bounds for graph diameter and eccentricities
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

Cited in

(28)

• Local construction and coloring of spanners of location aware unit disk graphs
• Approximating the average stretch factor of geometric graphs
• Minimum dilation stars
• On the dilation spectrum of paths, cycles, and trees
• Dilation-Optimal Edge Deletion in Polygonal Cycles
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Many distances in planar graphs
• Approximating the average stretch factor of geometric graphs
• Thresholding random geometric graph properties motivated by ad hoc sensor networks
• Bounded-degree plane geometric spanners in practice
• Dilation-optimal edge deletion in polygonal cycles
• scientific article; zbMATH DE number 7561700 (Why is no real title available?)
• Spanners in randomly weighted graphs: Euclidean case
• scientific article; zbMATH DE number 17663 (Why is no real title available?)
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• Linear time algorithm for optimal feed-link placement
• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• Testing Euclidean Spanners
• Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
• On the stretch factor of polygonal chains
• Connect the Dot: Computing Feed-Links with Minimum Dilation
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• A fast algorithm for approximating the detour of a polygonal chain.
• Deformable spanners and applications
• scientific article; zbMATH DE number 1809600 (Why is no real title available?)
• A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
• Distribution-sensitive construction of the greedy spanner

This page was built for publication: Approximating the Stretch Factor of Euclidean Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4507380)