Delaunay graphs are almost as good as complete graphs
From MaRDI portal
(Redirected from Publication:584279)
Recommendations
- scientific article; zbMATH DE number 140458
- On the average length of Delaunay triangulations
- There are planar graphs almost as good as the complete graph
- scientific article; zbMATH DE number 4155926
- There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
Cited in
(66)- Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity
- Sparse hop spanners for unit disk graphs
- Lower bounds on the dilation of plane spanners
- Generalizing geometric graphs
- There are plane spanners of degree 4 and moderate stretch factor
- A generalized hypergreedy algorithm for weighted perfect matching
- Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
- Constrained generalized Delaunay graphs are plane spanners
- Generating sparse 2—spanners
- Improved routing on the Delaunay triangulation
- Some properties of k-Delaunay and k-Gabriel graphs
- Approximating Euclidean distances by small degree graphs
- Constructing sparse spanners for most graphs in higher dimensions
- Small stretch ( , )-spanners in the streaming model
- Bounds for the CRDT conformal mapping algorithm
- Light orthogonal networks with constant geometric dilation
- Spanners of de Bruijn and Kautz graphs
- Spanners of underlying graphs of iterated line digraphs
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Tree spanners in planar graphs
- Red-black spanners for mixed-charging vehicular networks
- Plane hop spanners for unit disk graphs: simpler and better
- On the stabbing number of a random Delaunay triangulation
- Cycle bases of graphs and sampled manifolds
- Routing on heavy path WSPD spanners
- Upper and lower bounds for online routing on Delaunay triangulations
- Graph spanners in the streaming model: An experimental study
- NP-completeness of minimum spanner problems
- Toughness and Delaunay triangulations
- Upper and lower bounds for online routing on Delaunay triangulations
- There are planar graphs almost as good as the complete graph
- On sparse spanners of weighted graphs
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- scientific article; zbMATH DE number 140458 (Why is no real title available?)
- Empty-ellipse graphs
- Drawing graphs as spanners
- MIXED SPANNING TREES IN THEORY AND PRACTICE
- Beta-skeletons have unbounded dilation
- scientific article; zbMATH DE number 7765415 (Why is no real title available?)
- Lower bounds on the dilation of plane spanners
- Competitive online routing on Delaunay triangulations
- Local routing in sparse and lightweight geometric graphs
- Approximating \(k\)-spanner problems for \(k>2\)
- scientific article; zbMATH DE number 4155926 (Why is no real title available?)
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- Approximation of minimum weight spanners for sparse graphs
- Improved stretch factor of Delaunay triangulations of points in convex position
- Euclidean spanner graphs with degree four
- Tight stretch factors for L₁- and L_-Delaunay triangulations
- An exact algorithm for the minimum dilation triangulation problem
- Affine invariant triangulations
- A uniqueness theorem for Delaunay graphs
- On plane geometric spanners: a survey and open problems
- EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- On the stretch factor of Delaunay triangulations of points in convex position
- Improved routing on the Delaunay triangulation
- Dushnik-Miller dimension of TD-Delaunay complexes
- Emanation graph: a plane geometric spanner with Steiner points
- IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION
- A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
- Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation
- 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
- 10-Gabriel graphs are Hamiltonian
- Competitive online routing in geometric graphs
This page was built for publication: Delaunay graphs are almost as good as complete graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q584279)
