Proximity Drawability: A Survey (extended abstract)

Di Battista, Giuseppe and Lenhart, William and Liotta, Giuseppe (1995) Proximity Drawability: A Survey (extended abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 328-339 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_388).

Full text not available from this repository.

Abstract

Increasing attention has been given recently to drawings of graphs in which edges connect vertices based on some notion of proximity. Among such drawings are Gabriel, relative neighborhood, Delaunay, sphere of influence, and minimum spanning drawings. This paper attempts to survey the work that has been done to date on proximity drawings, along with some of the problems which remain open in this area.

Item Type:Conference Paper
Classifications:A General Literature > A.001 Introductory and Survey
P Styles > P.999 Others
ID Code:202

Repository Staff Only: item control page

References

P. K. Agarwal and J. Matousek. Relative Neighbourhood Graphs in Three Dimensions. Computational Geometry: Theory and application, 2, 1992, pp. 1-14.

P. Bose, G. Di Battista, W. Lenhart, and G. Liotta. Proximity Constraints and Representable Trees. Proc. of GD94.

P. Bose, W. Lenhart, and G. Liotta. Characterizing Proximity Trees. To appear in Algorithmica: Special Issue on Graph Drawing, also available as Tech. Rep. no. SOCS 93.9, School of Computer Science, McGill University.

B. Chazelle, H. Edelsbrunner, L. J. Guibas, J. E. Hershberger, R. Seidel, and M. Sharir. Slimming Down by Adding; Selecting Heavily Covered Points. Proc. ACM Symp. on Comp. Geom., 1990, pp. 116-127.

R. J. Cimikowski. Properties of Some Euclidean Proximity Graphs. Pattern Recognition Letters, 13, 1992, pp. 417-423.

M. de Berg, S. Carlsson and M.H. Overmars. A General Approach to Dominance in the Plane. Journal of Algorithms, 13, 1992, pp. 274-296.

B. Delaunay. Sur la Sphere vide. Bull. Acad. Sci. USSR(VII), 7, 1934, pp. 793-800.

G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis. Algorithms for Automatic Graph Drawing: An Annotated Bibliography. To appear in Computational Geometry: Theory and Applications.

G. Di Battista and L. Vismara. Angles of Planar Triangular Graphs. Proc. ACM Symposium on Theory of Computing, 1993, pp. 431-437.

M. B. Dillencourt. Realizability of Delaunay Triangulations. Information Proc. Letters, 33, 1990, pp. 283-287.

M. B. Dillencourt. Toughness and Delaunay Triangulations. Discrete and Computational Geometry, 5, 1990, pp. 575-601.

M. B. Dillencourt and W. D. Smith. Graph-Theoretical Conditions for Inscribability and Delaunay Realizability. Proc. CCCG '94, 1994, pp. 287-292.

P. Eades and S. Whitesides. The Realization Problem for Euclidean Minimum Spanning Trees is NP-hard. Proc. ACM Symposium on Computational Geometry, 1994, pp. 49-56.

H. ElGindy, G. Liotta, A. Lubiw, H. Meijer, and S.H. Whitesides. Recognizing Rectangle of Influence Drawable Graphs. Proc. of GD94.

K. R. Gabriel and R. R. Sokal. A New Statistical Approach to Geographical Analysis. Systematic Zoology, 18, 1969, pp. 54-64.

F. Harary. Graph Theory. Addison-Wesley Pub. Comp. 1969.

M. Garey and D. Johnson. A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, 1979.

R.H. Guting, O. Nurmi, and T. Ottmann. Fast Algorithms for Direct Enclosures and Direct Dominances. Journal of Algorithms, 10, 1989, pp. 170-186.

M. Ichino, J. Sklansky. The Relative Neighborhood Graph for Mixed Feature Variables. Pattern Recognition, 18, 2, 1985, pp. 161-167.

M. S. Jacobson, M. J. Lipman, and F. R. McMorris. Trees that are Sphere-of-Influence Graphs. University of Louisville, Tech. Rep. 0191/2, 1989.

J. W. Jaromczyk and G. T. Toussaint. Relative Neighborhood Graphs and Their Relatives. Proceedings of the IEEE, 80, 1992, pp. 1502-1517.

J. M. Keil Computing a subgraph of the minimum weight triangulation. Computational Geometry: Theory and Applications, 4, 1994, pp. 13-26.

D. G. Kirkpatrick and J. D. Radke. A Framework for Computational Morphology. Computational Geometry, G. T. Toussaint, Elsevier, Amsterdam, 1985, pp. 217-248.

P.M. Lankford. Regionalization: Theory and Alternative Algorithms. Geographical Analysis, 1, 1969, pp. 196-212.

A. Lubiw, and N. Sleumer, All Maximal Outerplanar Graphs are Relative Neighborhood Graphs. Proc. CCCG '93, 1993, pp. 198-203.

D. W. Matula and R. R. Sokal. Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the Plane. Geographical Analysis,

12, 3, 1980, pp. 205-222.

C. Monma and S. Suri. Transitions in Geometric Minimum Spanning Trees. Proc. ACM Symposium on Computational Geometry, 1991, pp. 239-249.

M. S. Paterson and F.F. Yao, On Nearest-Neighbor Graphs. Proc. ICALP '92, 1992, pp. 416-426.

M. H. Overmars and D. Wood. On Rectangular Visibility. Journal of Algorithms, 9, 1988, pp. 372-390.

J. D. Radke. On the shape of a set of points. Computational Morphology, ed. G. T. Toussaint, Elsevier, Amsterdam, 1988, pp. 105-136.

T.-H. Su and R.-Ch. Chang. The k-Gabriel Graphs and their Applications. Proc. International Symposium, SIGAL '90, 1990, pp. 66-75.

T.-H. Su and R.-Ch. Chang. Computing the k-relative neighborhood graphs in Euclidean Plane. Pattern Recognition, 24, 1991, pp. 231-239.

G. T. Toussaint. The Relative Neighborhood Graph of a Finite Planar Set. Pattern Recognition, 12, 1980, pp. 261-268.

G. T. Toussaint. A Graph-Theoretical Primal Sketch. Computational Morphology, ed. G. T. Toussaint, Elsevier, Amsterdam, 1988, pp. 229-260.

R. B. Urquhart. Some Properties of the Planar Euclidean Relative Neighbourhood Graph. Pattern Recognition Letters, 1, 1983, pp. 317-322.

R. C. Vetkamp. The y-Neighbourhood Graph. Computational Geometry: Theory and Applications, 1, 1992, pp. 227-246.