Lattice Spanners of Low Degree

DOI10.1007/978-3-319-29221-2_13zbMath1437.68186arXiv1602.04381OpenAlexW2281083481MaRDI QIDQ2795942

Adrian Dumitrescu, Anirban Ghosh

Publication date: 23 March 2016

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.04381

zbMATH Keywords

geometric graphplanar latticestretch factorplane spannervertex dilation

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Related Items (3)

Lower Bounds on the Dilation of Plane Spanners ⋮ Lattice spanners of low degree ⋮ A note on optimal degree-three spanners of the square lattice

Cites Work

• Unnamed Item
• Unnamed Item
• On plane geometric spanners: a survey and open problems
• On bounded degree plane strong geometric spanners
• 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
• Computing a minimum-dilation spanning tree is NP-hard
• 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
• A fast algorithm for approximating the detour of a polygonal chain.
• There are planar graphs almost as good as the complete graph
• Degree-constrained spanners for multidimensional grids
• Most finite point sets in the plane have dilation \(>1\)
• There are plane spanners of degree 4 and moderate stretch factor
• Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
• The geometric dilation of finite point sets
• The Stretch Factor of the Delaunay Triangulation Is Less than 1.998
• Geometric Spanner Networks
• Plane Spanners of Maximum Degree Six
• DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• EFFICIENT CONSTRUCTION OF LOW WEIGHTED BOUNDED DEGREE PLANAR SPANNER
• CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
• Grid spanners
• Lower Bounds on the Dilation of Plane Spanners

This page was built for publication: Lattice Spanners of Low Degree