Classes of graphs which approximate the complete Euclidean graph
From MaRDI portal
Publication:1186079
DOI10.1007/BF02187821zbMath0751.52004WikidataQ56047089 ScholiaQ56047089MaRDI QIDQ1186079
Publication date: 28 June 1992
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131177
Analysis of algorithms and problem complexity (68Q25) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Distance in graphs (05C12) Elementary problems in Euclidean geometries (51M04)
Related Items
Constrained generalized Delaunay graphs are plane spanners ⋮ Euclidean spanner graphs with degree four ⋮ Euclidean Steiner Spanners: Light and Sparse ⋮ On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ Improved bounds on the spanning ratio of the theta-5-graph ⋮ Routing on heavy-path WSPD-spanners ⋮ Approximating geometric bottleneck shortest paths ⋮ Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles ⋮ EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION ⋮ On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ A GEOMETRIC SPANNER OF SEGMENTS ⋮ Good triangulations yield good tours ⋮ Truly Optimal Euclidean Spanners ⋮ Competitive Online Routing on Delaunay Triangulations ⋮ On plane geometric spanners: a survey and open problems ⋮ Ordered theta graphs ⋮ Unnamed Item ⋮ Improved routing on the Delaunay triangulation ⋮ On path-greedy geometric spanners ⋮ On the stretch factor of Delaunay triangulations of points in convex position ⋮ Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\) ⋮ On the spanning and routing ratio of the directed theta-four graph ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ New constructions of SSPDs and their applications ⋮ Compact and low delay routing labeling scheme for unit disk graphs ⋮ Local routing algorithms on Euclidean spanners with small diameter ⋮ Geometric Spanner of Objects under L 1 Distance ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Spanners of Additively Weighted Point Sets ⋮ Computing the Greedy Spanner in Near-Quadratic Time ⋮ New approximation algorithms for minimum cycle bases of graphs ⋮ Spanners of additively weighted point sets ⋮ Unnamed Item ⋮ On certain geometric properties of the Yao-Yao graphs ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation ⋮ On bounded degree plane strong geometric spanners ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ A fast algorithm for approximating the detour of a polygonal chain. ⋮ Sparse communication networks and efficient routing in the plane ⋮ Sparse geometric graphs with small dilation ⋮ I/O-efficient algorithms for computing planar geometric spanners ⋮ Geometric Spanner of Segments ⋮ Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations ⋮ Local properties of geometric graphs ⋮ Light Euclidean Spanners with Steiner Points ⋮ Disordered contact networks in jammed packings of frictionless disks ⋮ Improved spanning ratio for low degree plane spanners ⋮ A generalized hypergreedy algorithm for weighted perfect matching ⋮ A simple and efficient kinetic spanner ⋮ Stable roommates spanner ⋮ Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs ⋮ Most finite point sets in the plane have dilation \(>1\) ⋮ The \(\varTheta_5\)-graph is a spanner ⋮ Minimum weight convex Steiner partitions ⋮ A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation ⋮ On a family of strong geometric spanners that admit local routing strategies ⋮ The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study ⋮ Sigma-local graphs ⋮ Bounds for the CRDT conformal mapping algorithm ⋮ Improved local algorithms for spanner construction ⋮ Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces ⋮ Lattice Spanners of Low Degree ⋮ A distributed algorithm to maintain a proximity communication network among mobile agents using the Delaunay triangulation ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Empty region graphs ⋮ Constrained routing between non-visible vertices ⋮ Self-stabilizing metric graphs ⋮ Light orthogonal networks with constant geometric dilation ⋮ DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE ⋮ Lattice spanners of low degree ⋮ Improved Accuracy of Monotone Finite Difference Schemes on Point Clouds and Regular Grids ⋮ Unnamed Item ⋮ A simple, faster method for kinetic proximity problems ⋮ An \(O(1)\)-approximation algorithm for the 2-dimensional geometric freeze-tag problem ⋮ There are plane spanners of degree 4 and moderate stretch factor ⋮ Approximating Euclidean distances by small degree graphs
Cites Work
