scientific article; zbMATH DE number 4155925

MaRDI QIDQ3484375zbMATH OpenFDO

Authors

Publication date 1989

zbMATH Keywords

network designplanar graphsapproximation of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Network design and communication in computer systems (68M10)

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 4070353
• Classes of graphs which approximate the complete Euclidean graph
• Triangulating planar graphs while minimizing the maximum degree

Cited in

(32)

• Sparse hop spanners for unit disk graphs
• Lower bounds on the dilation of plane spanners
• Vertex fault-tolerant spanners for weighted points in polygonal domains
• Constrained generalized Delaunay graphs are plane spanners
• Generating sparse 2—spanners
• Small stretch ( , )-spanners in the streaming model
• Euclidean Steiner spanners: light and sparse
• On exclusion regions for optimal triangulations
• On a linear program for minimum-weight triangulation
• Light orthogonal networks with constant geometric dilation
• Vertex Fault-Tolerant Geometric Spanners for Weighted Points
• New results on MWT subgraphs
• scientific article; zbMATH DE number 7561700 (Why is no real title available?)
• Graph spanners in the streaming model: An experimental study
• There are planar graphs almost as good as the complete graph
• On sparse spanners of weighted graphs
• Beta-skeletons have unbounded dilation
• scientific article; zbMATH DE number 7765415 (Why is no real title available?)
• Lower bounds on the dilation of plane spanners
• Solving large-scale minimum-weight triangulation instances to provable optimality
• An improved upper bound for the universal TSP on the grid
• Constructing competitive tours from local information
• Good triangulations yield good tours
• Minimum weight pseudo-triangulations
• Euclidean spanner graphs with degree four
• On plane geometric spanners: a survey and open problems
• On the stretch factor of polygonal chains
• A fast heuristic for approximating the minimum weight triangulation
• Triangulations intersect nicely
• Constructing competitive tours from local information
• There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
• Competitive online routing in geometric graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3484375)