Approximating Euclidean distances by small degree graphs

Althöfer, I.; Das, G.; Dobkin, D.; Joseph, D., Generating sparse spanners for weighted graphs,Proc. Second Scandinavian Workshop on Algorithm Theory, 1990, pp. 26–37.

Althöfer, I.; Das, G.; Dobkin, D.; Joseph, D.; Soares, J., On sparse spanners of weighted graphs,Discrete Comput. Geom. 9 (1993), 81–100.

Chew, L. P., There is a planar graph almost as good as the complete graph,Proc. Second Symposium on Computational Geometry, 1986, pp. 169–177.

Conway, J. H.; Sloane, N. J. A.,Sphere Packings, Lattices, and Groups, Springer-Verlag, New York, 1988.

Dobkin, P. D.; Friedman, S. J.; Supowit, K. J., Delaunay graphs are almost as good as complete graphs,Discrete Comput. Geom. 5 (1990), 399–407.

Kabatiansky, G. A.; Levenshtein, V. I., Bounds for packings on a sphere and in space,Problems Inform. Transmission 14 (1978), 1–17.

Keil, J. M., Approximating the complete Euclidean graph,Proc. First Scandinavian Workshop on Algorithm Theory, 1988, pp. 208–213.

Keil, J. M.; Gutwin, C. A., Classes of graphs which approximate the complete Euclidean graph,Discrete Comput. Geom. 7 (1992), 13–28.

Levcopoulos, C.; Lingas, A., There are planar graphs almost as good as the complete graphs and as short as the minimum spanning trees,Proc. Symposium on Optimal Algorithms, 1989, pp, 9–13.

Nisan, N., Personal communication, 1990.

Peleg, D.; Schäffer, A., Graphs spanners,J. Graph Theory,13 (1989), 99–116.

Rankin, R. A., The closest packing of spherical caps inn dimensions,Proc. Glasgow Math. Assoc. 2 (1955), 139–144.

Ruppert, J.; Seidel, R., Approximating thed-dimensional complete Euclidean graph,Proc. Canadian Conference on Computational Geometry, 1991, pp. 207–210.

Salowe, J. S., Construction of multidimensional spanner graphs, with applications to minimum spanning trees,Proc. Seventh Symposium on Computational Geometry, 1991, pp. 256–261.

Salowe, J., On Euclidean spanners graphs with small degree,Proc. 8th ACM Symposium on Computational Geometry, 1992, pp. 192–201.

Soares, J., Approximating metrics by graphs, Manuscript, 1990.

Vaidya, P. M., AnO(n logn) algorithm for the all-nearest-neighbors problem,Discrete Comput. Geom. 4 (1989), 101–115.

Vaidya, P. M., A sparse graph almost as good as the complete graph on points ink dimensions,Discrete Comput. Geom. 6 (1991), 369–381.