On the dilation spectrum of paths, cycles, and trees

DOI10.1016/J.COMGEO.2009.03.004MaRDI QIDQ833719zbMATH OpenOpenAlexFDO

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

networkdistributioncomputational geometrydilationspectrumgeometric graphstretch factor

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• Dilation-optimal edge deletion in polygonal cycles
• Minimum dilation stars
• Minimum dilation stars
• The geometric dilation of finite point sets

Cites work

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

Cited in

(4)

• scientific article; zbMATH DE number 7561700 (Why is no real title available?)
• Minimum dilation stars
• On the stretch factor of polygonal chains
• Algorithms and Computation

This page was built for publication: On the dilation spectrum of paths, cycles, and trees

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