Euclidean spanner graphs with degree four

DOI10.1016/0166-218X(94)90133-3zbMath0812.68104MaRDI QIDQ1336638

Jeffrey S. Salowe

Publication date: 28 November 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

\(t\)-spanner

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Related Items (3)

A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees ⋮ Degree-bounded minimum spanning trees ⋮ There are plane spanners of degree 4 and moderate stretch factor

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay graphs are almost as good as complete graphs
• Efficient algorithms for agglomerative hierarchical clustering methods
• Classes of graphs which approximate the complete Euclidean graph
• On sparse spanners of weighted graphs
• Approximating Euclidean distances by small degree graphs
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• There are planar graphs almost as good as the complete graph
• How Small Is a Unit Ball?
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS

This page was built for publication: Euclidean spanner graphs with degree four