scientific article; zbMATH DE number 4155925

MaRDI QIDQ3484375zbMATHFDO

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)

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

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)