Light orthogonal networks with constant geometric dilation

DOI10.1016/j.jda.2008.07.007zbMath1263.68120OpenAlexW1991315286MaRDI QIDQ1013080

Adrian Dumitrescu, Csaba D. Tóth

Publication date: 16 April 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.07.007

zbMATH Keywords

network designdetourstretch factorgeometric dilationorthogonal networkplane straight line graphSteiner vertices

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items (2)

Euclidean Steiner Spanners: Light and Sparse ⋮ Minimum weight convex Steiner partitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Multidimensional divide-and-conquer
• Delaunay graphs are almost as good as complete graphs
• Constructing plane spanners of bounded degree and low weight
• On the geometric dilation of closed curves, graphs, and point sets
• Sparse geometric graphs with small dilation
• Two probabilistic results on rectilinear Steiner trees
• Classes of graphs which approximate the complete Euclidean graph
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• On sparse spanners of weighted graphs
• Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
• A fast algorithm for approximating the detour of a polygonal chain.
• There are planar graphs almost as good as the complete graph
• The minimum Manhattan network problem: Approximations and exact solutions
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• The geometric dilation of finite point sets
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Geometric Spanner Networks
• Orthogonal Range Searching in Linear and Almost-Linear Space
• New Data Structures for Orthogonal Range Queries
• Dynamic orthogonal segment intersection search
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

This page was built for publication: Light orthogonal networks with constant geometric dilation