scientific article; zbMATH DE number 5542484

MaRDI QIDQ3619930zbMATH OpenFDO

Authors Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Michael Soss, Pankaj K. Agarwal, Micha Sharir

Publication date 14 April 2009

zbMATH Keywords

complete Euclidean graphEuclidean spaceHopcroft's problem

Mathematics Subject Classification ID

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

Recommendations

• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• scientific article; zbMATH DE number 2086390
• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• Spanning ratio and maximum detour of rectilinear paths in the \(L _{1}\) plane
• On spanning cycles, paths and trees
• Algorithms and Computation
• scientific article; zbMATH DE number 1156578
• scientific article; zbMATH DE number 176745
• Computing minimum dilation spanning trees in geometric graphs
• Spanning trees, Euler tours, medial graphs, left-right paths and cycle spaces

Cited in

(10)

• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
• 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
• Computing the Maximum Detour of a Plane Graph in Subquadratic Time
• Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
• scientific article; zbMATH DE number 2086390 (Why is no real title available?)
• Lower bounds on the dilation of plane spanners
• Bottleneck detour tree of points on a path
• Geometric dilation of closed planar curves: New lower bounds

This page was built for publication:

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