On the dilation spectrum of paths, cycles, and trees

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

Rolf Klein, Giri Narasimhan, Christian Knauer, 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

network; distribution; spectrum; dilation; geometric graph; computational geometry; stretch factor

Mathematics Subject Classification ID

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

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)

05C62: Graph representations (geometric and intersection representations, etc.)

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