There are planar graphs almost as good as the complete graph
From MaRDI portal
Publication:1823959
For a graph G represented in the plane (perhaps with edges intersecting internally) the length of a path joining two vertices of G is here regarded as the sum of the straight-line distances between successive vertices on the path. Given a set S of points in the plane, the complete graph on S has the property that for each pair A, B in S there exists an A-B path of length the straight-line distance between A and B. (The complete graph is unique with this property, if the points of S are in general position.) In this paper it is shown that there is a planar graph G on S with the property: for each pair A, B in S, there exists an A-B path of length at most twice the straight-line distance between A and B. The graph G is a type of Delaunay triangulation. It has 0 (ISI) edges (compare 0 \((ISI^ 2)\) for the complete graph). Applications are discussed to network design and motion planning.
Recommendations
- 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
- scientific article; zbMATH DE number 4155925
- Delaunay graphs are almost as good as complete graphs
- Classes of graphs which approximate the complete Euclidean graph
Cites work
- A sweepline algorithm for Voronoi diagrams
- Constrained Delaunay triangulations
- Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
- Delaunay graphs are almost as good as complete graphs
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- Two algorithms for constructing a Delaunay triangulation
Cited in
(98)- Light orthogonal networks with constant geometric dilation
- 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
- Euclidean spanner graphs with degree four
- Sorting helps for Voronoi diagrams
- Beta-skeletons have unbounded dilation
- Constrained generalized Delaunay graphs are plane spanners
- An exact algorithm for the minimum dilation triangulation problem
- Tree spanners of bounded degree graphs
- Cone-based spanners of constant degree
- Strong matching of points with geometric shapes
- Balancing minimum spanning trees and shortest-path trees
- On shape Delaunay tessellations
- Graph spanners: a tutorial review
- Path-length analysis for grid-based path planning
- On the spanning and routing ratios of the directed _6-graph
- Spanning properties of Theta-Theta-6
- Dushnik-Miller dimension of TD-Delaunay complexes
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Packing plane spanning graphs with short edges in complete geometric graphs
- There are plane spanners of degree 4 and moderate stretch factor
- Good triangulations yield good tours
- Upper and lower bounds for online routing on Delaunay triangulations
- The minimum Manhattan network problem: Approximations and exact solutions
- On approximating tree spanners that are breadth first search trees
- Emanation graph: a plane geometric spanner with Steiner points
- Lattice spanners of low degree
- Lattice spanners of low degree
- Gabriel triangulations and angle-monotone graphs: local routing and recognition
- Network flow spanners
- Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
- Yao graphs span theta graphs
- Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
- Upper and lower bounds for online routing on Delaunay triangulations
- scientific article; zbMATH DE number 4155926 (Why is no real title available?)
- On plane geometric spanners: a survey and open problems
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- scientific article; zbMATH DE number 3954891 (Why is no real title available?)
- A Tight Lower Bound on the Size of Planar Permutation Networks
- Collective additive tree spanners for circle graphs and polygonal graphs
- Constructing linear-sized spectral sparsification in almost-linear time
- Tight stretch factors for L₁- and L_-Delaunay triangulations
- The greedy spanner is existentially optimal
- Improved routing on the Delaunay triangulation
- Euclidean Steiner spanners: light and sparse
- Truly Optimal Euclidean Spanners
- Distribution-sensitive construction of the greedy spanner
- Additive Spanners for Circle Graphs and Polygonal Graphs
- Competitive routing in the half-\(\theta_6\)-graph
- Delaunay graphs are almost as good as complete graphs
- A note on optimal degree-three spanners of the square lattice
- Light Euclidean Spanners with Steiner Points
- Lower bounds on the dilation of plane spanners
- The price of order
- The price of order
- A simple and efficient kinetic spanner
- Drawing graphs as spanners
- Hamiltonicity for convex shape Delaunay and Gabriel graphs
- Lower bounds for computing geometric spanners and approximate shortest paths
- Improved routing on the Delaunay triangulation
- Edge sparsification for geometric tour problems
- On the spanning and routing ratio of the directed theta-four graph
- Local routing algorithms on Euclidean spanners with small diameter
- Vertex Fault-Tolerant Geometric Spanners for Weighted Points
- Vertex fault-tolerant spanners for weighted points in polygonal domains
- Online Spanners in Metric Spaces
- 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
- A unified framework for light spanners
- Bounded-degree plane geometric spanners in practice
- Routing on heavy path WSPD spanners
- New results on edge-coloring and total-coloring of split graphs
- Spectral sparsification via bounded-independence sampling
- A unified framework of light spanners. I: Fast (yet optimal) constructions
- Truly optimal Euclidean spanners
- The tight spanning ratio of the rectangle Delaunay triangulation
- Online spanners in metric spaces
- The exact spanning ratio of the parallelogram Delaunay graph
- Small-space spectral sparsification via bounded-independence sampling
- Online Euclidean spanners
- Optimal spanners for axis-aligned rectangles
- On euclidean Steiner (1+)-spanners
- Light Euclidean Steiner spanners in the plane
- On the edge crossings of the greedy spanner
- Routing from pentagon to octagon Delaunay graphs
- Exact algorithms for minimum dilation triangulation
- Demand-aware plane spanners of bounded degree
- Fixed-orientation equilateral triangle matching of point sets
- On the spanning and routing ratios of the directed _6-graph
- Improved bounds on the spanning ratio of the theta-5-graph
- Graph spanners in the streaming model: An experimental study
- Small stretch ( , )-spanners in the streaming model
- Computing the greedy spanner in linear space
- Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
- Towards tight bounds on theta-graphs: more is not always better
- Combinatorial network abstraction by trees and distances
This page was built for publication: There are planar graphs almost as good as the complete graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1823959)
