Proximity Constraints and Representable Trees (extended abstract)

Bose, Prosenjit and Di Battista, Giuseppe and Lenhart, William and Liotta, Giuseppe (1995) Proximity Constraints and Representable Trees (extended abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 340-351 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_389).

Full text not available from this repository.

Abstract

A family of proximity drawings of graphs called open and closed \beta-drawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete characterizations of which trees admit open \beta-drawings for 0 \leq \beta \leq \frac{1}{2 sin^2(\pi/5)} and \frac{1}{cos(2\pi/5)} < \beta < \infty or closed \beta-drawings0 \leq \beta < \frac{1}{2 sin^2(\pi/5)} and \frac{1}{cos(2\pi/5)} \leq \beta \leq \infty are given as well as partial characterizations for other values of \beta. For \beta < \infty in the intervals in which complete characterizations are given, it can be determined in linear time whether a tree admits an open or closed \beta-drawing, and, if so, such a drawing can be computed in linear time in the real RAM model. Finally, a complete characterization of all graphs which admit closed strip drawings is given.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_389
Classifications:M Methods > M.900 Tree
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
ID Code:203

Repository Staff Only: item control page

References

J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Elsevier Science, New York, 1976.

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

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

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, W. Lenhart, G. Liotta. Proximity Drawability: a Survey. Proc. GD94, 1994.

G. Di Battista and L. Vismara. Angles of Planar Triangualr Graphs. Proc. STOC '93, 1993, pp. 431-437.

P. Eades, T. Lin, and X. Lin. Two Tree Drawing Conventions. Int. J. of Comp. Geom. and Appl., 3, 1993, pp. 133-153.

P. Eades. Drawing Free Trees. Bull. of the Inst. of Comb. and its appl., 1992, pp. 10-36.

P. Eades and S. Whitesides. The Realization Problem of Euclidean Minimum Spanning Trees in NP-hard. Proc. ACM Symp. on Comp. Geom., 1994.

I. Fary. On Straight Lines Representation of Planar Graphs. Acta Sci. Math. Szeged, 11, 1948, pp. 229-233.

H. de Fraysseix, J. Pach, and R. Pollack. Small Sets Supporting Fary Embeddings of Planar Graphs. Proc. STOC '88, 1988, pp. 426-433.

H. de Fraysseix, J. Pach, and R. Pollack. How to DRaw a Planar Graph on a Grid. Combinatorica, 10, 1990, pp. 41-51.

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

G. Kant. Drawing Planar Graphs Using the lmc-ordering. Proc. FOCS '92, 1992, pp. 101-110.

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

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

S. Malitz and A. Papakostas. On the Angular Resolution of Planar Graphs. Proc. STOC '92, 1992, pp. 527-538.

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, 1980, pp. 205-222.

C. Monma and S. Suri. Transitions in Geometric Minimum Spanning Trees. Proc. ACM Symp. on Comp. Geom., 1991, pp. 239-249.

F. P. Preparata and M. I. Shamos, Computational Geometry - an Introduction. Springer-Verlag, New York, 1985.

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

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.

W. T. Tutte, Convex Representations of Graphs. Proc. London Math. Soc., 10, 1960, pp. 304-320.

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