Computing the maximum detour and spanning ratio of planar paths, trees, and cycles

DOI10.1007/3-540-45841-7_20MaRDI QIDQ4736844zbMATH OpenFDO

Authors Stefan Langerman, Pat Morin, Michael Soss

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2285/22850250.htm

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 5542484
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Spanning ratio and maximum detour of rectilinear paths in the \(L _{1}\) plane
• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• Computing the Maximum Detour of a Plane Graph in Subquadratic Time

Cited in

(13)

• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• Computing the maximum detour of a plane geometric graph in subquadratic time
• Spanning ratio and maximum detour of rectilinear paths in the \(L _{1}\) plane
• Connect the Dot: Computing Feed-Links with Minimum Dilation
• Computing the Maximum Detour of a Plane Graph in Subquadratic Time
• scientific article; zbMATH DE number 5542484 (Why is no real title available?)
• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• Dilation-Optimal Edge Deletion in Polygonal Cycles
• Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• On the geometric dilation of closed curves, graphs, and point sets
• Minimum dilation stars
• Geometric dilation of closed planar curves: New lower bounds

This page was built for publication: Computing the maximum detour and spanning ratio of planar paths, trees, and cycles

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