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