Delaunay graphs are almost as good as complete graphs
From MaRDI portal
Publication:584279
DOI10.1007/BF02187801zbMath0693.05045OpenAlexW2031874971MaRDI QIDQ584279
Kenneth J. Supowit, David P. Dobkin, Steven J. Friedman
Publication date: 1990
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131128
Related Items (61)
Beta-skeletons have unbounded dilation ⋮ Constrained generalized Delaunay graphs are plane spanners ⋮ Sparse hop spanners for unit disk graphs ⋮ Euclidean spanner graphs with degree four ⋮ Spanners of de Bruijn and Kautz graphs ⋮ Spanners of underlying graphs of iterated line digraphs ⋮ Constructing sparse spanners for most graphs in higher dimensions ⋮ Graph spanners in the streaming model: An experimental study ⋮ Local routing in sparse and lightweight geometric graphs ⋮ Competitive online routing in geometric graphs ⋮ Small stretch \((\alpha ,\beta )\)-spanners in the streaming model ⋮ Upper and Lower Bounds for Online Routing on Delaunay Triangulations ⋮ EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION ⋮ Generating sparse 2—spanners ⋮ IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION ⋮ On the stabbing number of a random Delaunay triangulation ⋮ Competitive Online Routing on Delaunay Triangulations ⋮ On plane geometric spanners: a survey and open problems ⋮ Upper and lower bounds for online routing on Delaunay triangulations ⋮ An exact algorithm for the minimum dilation triangulation problem ⋮ Improved routing on the Delaunay triangulation ⋮ Dushnik-Miller dimension of TD-Delaunay complexes ⋮ On the stretch factor of Delaunay triangulations of points in convex position ⋮ Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\) ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Unnamed Item ⋮ Plane hop spanners for unit disk graphs: simpler and better ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation ⋮ Unnamed Item ⋮ Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations ⋮ Classes of graphs which approximate the complete Euclidean graph ⋮ Improved spanning ratio for low degree plane spanners ⋮ 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 generalized hypergreedy algorithm for weighted perfect matching ⋮ Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs ⋮ Tree spanners in planar graphs ⋮ A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation ⋮ Bounds for the CRDT conformal mapping algorithm ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces ⋮ MIXED SPANNING TREES IN THEORY AND PRACTICE ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Cycle bases of graphs and sampled manifolds ⋮ Generalizing Geometric Graphs ⋮ Improved stretch factor of Delaunay triangulations of points in convex position ⋮ Drawing graphs as spanners ⋮ Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity ⋮ Light orthogonal networks with constant geometric dilation ⋮ A sparse graph almost as good as the complete graph on points in \(k\) dimensions ⋮ DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE ⋮ Affine invariant triangulations ⋮ There are planar graphs almost as good as the complete graph ⋮ Toughness and Delaunay triangulations ⋮ NP-completeness of minimum spanner problems ⋮ There are plane spanners of degree 4 and moderate stretch factor ⋮ Approximating Euclidean distances by small degree graphs ⋮ 10-Gabriel graphs are Hamiltonian
Cites Work
This page was built for publication: Delaunay graphs are almost as good as complete graphs
