There are planar graphs almost as good as the complete graph
From MaRDI portal
Publication:1823959
DOI10.1016/0022-0000(89)90044-5zbMath0682.05032OpenAlexW2139391136MaRDI QIDQ1823959
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
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Beta-skeletons have unbounded dilation, On approximating tree spanners that are breadth first search trees, 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, YAO GRAPHS SPAN THETA GRAPHS, Graph spanners in the streaming model: An experimental study, Small stretch \((\alpha ,\beta )\)-spanners in the streaming model, Optimal Local Routing on Delaunay Triangulations Defined by Empty Equilateral Triangles, Upper and Lower Bounds for Online Routing on Delaunay Triangulations, On the spanning and routing ratios of the directed \(\Theta_6\)-graph, Additive Spanners for Circle Graphs and Polygonal Graphs, Sorting helps for Voronoi diagrams, Balancing minimum spanning trees and shortest-path trees, Good triangulations yield good tours, Truly Optimal Euclidean Spanners, Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time, On plane geometric spanners: a survey and open problems, Spanning properties of Theta-Theta-6, 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, Computing the greedy spanner in linear space, 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\), Tree spanners of bounded degree graphs, On the spanning and routing ratio of the directed theta-four graph, Approximation of minimum weight spanners for sparse graphs, Local routing algorithms on Euclidean spanners with small diameter, Gabriel Triangulations and Angle-Monotone Graphs: Local Routing and Recognition, Vertex Fault-Tolerant Geometric Spanners for Weighted Points, Cone-based spanners of constant degree, Strong matching of points with geometric shapes, Higher-order triangular-distance Delaunay graphs: graph-theoretical properties, Online Spanners in Metric Spaces, Towards tight bounds on theta-graphs: more is not always better, The minimum Manhattan network problem: Approximations and exact solutions, Unnamed Item, Emanation graph: a plane geometric spanner with Steiner points, Collective additive tree spanners for circle graphs and polygonal graphs, Unnamed Item, Tight stretch factors for \(L_1\)- and \(L_\infty\)-Delaunay triangulations, Light Euclidean Spanners with Steiner Points, Classes of graphs which approximate the complete Euclidean graph, Combinatorial network abstraction by trees and distances, A simple and efficient kinetic spanner, Distribution-sensitive construction of the greedy spanner, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Lower bounds for computing geometric spanners and approximate shortest paths, Optimal spanners for axis-aligned rectangles, On shape Delaunay tessellations, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Graph spanners: a tutorial review, Network flow spanners, Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces, Lattice Spanners of Low Degree, Lower Bounds on the Dilation of Plane Spanners, Vertex fault-tolerant spanners for weighted points in polygonal domains, The Greedy Spanner Is Existentially Optimal, The Price of Order, The Price of Order, Drawing graphs as spanners, Hamiltonicity for convex shape Delaunay and Gabriel graphs, Fixed-orientation equilateral triangle matching of point sets, Light orthogonal networks with constant geometric dilation, DELAUNAY AND DIAMOND TRIANGULATIONS CONTAIN SPANNERS OF BOUNDED DEGREE, Lattice spanners of low degree, Path-length analysis for grid-based path planning, Unnamed Item, A note on optimal degree-three spanners of the square lattice, There are plane spanners of degree 4 and moderate stretch factor
Cites Work
