On the dilation spectrum of paths, cycles, and trees

DOI10.1016/j.comgeo.2009.03.004zbMath1200.05229OpenAlexW2059932006MaRDI QIDQ833719

Giri Narasimhan, Christian Knauer, Rolf Klein, Michiel H. M. Smid

Publication date: 14 August 2009

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2009.03.004

zbMATH Keywords

networkdistributionspectrumdilationgeometric graphcomputational geometrystretch factor

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Unnamed Item, On the Stretch Factor of Polygonal Chains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Computing a minimum-dilation spanning tree is NP-hard
• \(\epsilon\)-nets and simplex range queries
• The geometry of graphs and some of its algorithmic applications
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Geometric Spanner Networks
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• Computing the Maximum Detour of a Plane Graph in Subquadratic Time
• Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Graph spanners
• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Approximating the Stretch Factor of Euclidean Graphs