Lattice spanners of low degree
From MaRDI portal
Publication:2821117
DOI10.1142/S1793830916500518zbMath1352.52021MaRDI QIDQ2821117
Adrian Dumitrescu, Anirban Ghosh
Publication date: 16 September 2016
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Inequalities and extremum problems in real or complex geometry (51M16) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)
Related Items (3)
Sparse hop spanners for unit disk graphs ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Unnamed Item
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
- Lattice Spanners of Low Degree
- 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
- Lower Bounds on the Dilation of Plane Spanners
This page was built for publication: Lattice spanners of low degree
