There are planar graphs almost as good as the complete graph
From MaRDI portal
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
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- 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
- Two algorithms for constructing a Delaunay triangulation
Cited in
(84)- Path-length analysis for grid-based path planning
- On approximating tree spanners that are breadth first search trees
- Classes of graphs which approximate the complete Euclidean graph
- Approximation of minimum weight spanners for sparse graphs
- Beta-skeletons have unbounded dilation
- On the spanning and routing ratios of the directed \(\Theta_6\)-graph
- Gabriel triangulations and angle-monotone graphs: local routing and recognition
- There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
- Constrained generalized Delaunay graphs are plane spanners
- The greedy spanner is existentially optimal
- DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE
- Improved bounds on the spanning ratio of the theta-5-graph
- On the spanning and routing ratios of the directed \(\varTheta_6\)-graph
- scientific article; zbMATH DE number 4155926 (Why is no real title available?)
- Dushnik-Miller dimension of TD-Delaunay complexes
- Local routing algorithms on Euclidean spanners with small diameter
- scientific article; zbMATH DE number 3954891 (Why is no real title available?)
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- On the stretch factor of Delaunay triangulations of points in convex position
- Delaunay graphs are almost as good as complete graphs
- Combinatorial network abstraction by trees and distances
- Good triangulations yield good tours
- Computing the greedy spanner in linear space
- Tree spanners of bounded degree graphs
- Spanning properties of Theta-Theta-6
- Euclidean spanner graphs with degree four
- Improved routing on the Delaunay triangulation
- Lattice spanners of low degree
- Light orthogonal networks with constant geometric dilation
- Collective additive tree spanners for circle graphs and polygonal graphs
- Fixed-orientation equilateral triangle matching of point sets
- Balancing minimum spanning trees and shortest-path trees
- On plane geometric spanners: a survey and open problems
- Upper and lower bounds for online routing on Delaunay triangulations
- The minimum Manhattan network problem: Approximations and exact solutions
- Vertex Fault-Tolerant Geometric Spanners for Weighted Points
- Sorting helps for Voronoi diagrams
- An exact algorithm for the minimum dilation triangulation problem
- Lower bounds on the dilation of plane spanners
- Graph spanners: a tutorial review
- Graph spanners in the streaming model: An experimental study
- Cone-based spanners of constant degree
- Strong matching of points with geometric shapes
- Lower bounds for computing geometric spanners and approximate shortest paths
- Additive Spanners for Circle Graphs and Polygonal Graphs
- Connections between Theta-graphs, Delaunay triangulations, and orthogonal surfaces
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Constructing linear-sized spectral sparsification in almost-linear time
- Towards tight bounds on theta-graphs: more is not always better
- On shape Delaunay tessellations
- Truly Optimal Euclidean Spanners
- Optimal local routing on Delaunay triangulations defined by empty equilateral triangles
- Optimal spanners for axis-aligned rectangles
- Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations
- Distribution-sensitive construction of the greedy spanner
- Competitive routing in the half-\(\theta_6\)-graph
- Higher-order triangular-distance Delaunay graphs: graph-theoretical properties
- Hamiltonicity for convex shape Delaunay and Gabriel graphs
- There are plane spanners of degree 4 and moderate stretch factor
- Small stretch \((\alpha ,\beta )\)-spanners in the streaming model
- Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences
- Yao graphs span theta graphs
- A simple and efficient kinetic spanner
- Euclidean Steiner spanners: light and sparse
- A unified framework for light spanners
- Routing on heavy path WSPD spanners
- Bounded-degree plane geometric spanners in practice
- Lattice spanners of low degree
- New results on edge-coloring and total-coloring of split graphs
- A note on optimal degree-three spanners of the square lattice
- A Tight Lower Bound on the Size of Planar Permutation Networks
- Network flow spanners
- Improved routing on the Delaunay triangulation
- Online Spanners in Metric Spaces
- Emanation graph: a plane geometric spanner with Steiner points
- Edge sparsification for geometric tour problems
- Drawing graphs as spanners
- Packing plane spanning graphs with short edges in complete geometric graphs
- Upper and lower bounds for online routing on Delaunay triangulations
- Light Euclidean Spanners with Steiner Points
- On the spanning and routing ratio of the directed theta-four graph
- Vertex fault-tolerant spanners for weighted points in polygonal domains
- The price of order
- The price of order
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)
