Abstract
A family of proximity drawings of graphs called open and closed β-drawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete characterizations of which trees admit open β-drawings for \(0 \leqslant \beta \leqslant \tfrac{1}{{2sin^2 (\pi /5)}}\)and \(\tfrac{1}{{cos(2\pi /5)}} < \beta < \infty \)or closed β-drawings for \(0 \leqslant \beta < \tfrac{1}{{2sin^2 (\pi /5)}}\)and \(\tfrac{1}{{cos(2\pi /5)}}0 \leqslant \beta \leqslant \infty \)are given, as well as partial characterizations for other values of β. For β<∞ in the intervals in which complete characterizations are given, it can be determined in linear time whether a tree admits an open or closed β-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.
Research supported in part by NSERC and FCAR, by Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo of the Italian National Research Council (CNR).
Chapter PDF
Similar content being viewed by others
References
J. A. Bondy and U. S. R. Murty. Graph Theory with Applications. Elsevier Science, New York, 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 Triangular 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 for Euclidean Minimum Spanning Trees is 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 Embbeddings 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. Urquhart. Some Properties of the Planar Euclidean Relative Neighbourhood Graph. Pattern Recognition Letters, 1, 1983, pp. 317–322.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bose, P., Di Battista, G., Lenhart, W., Liotta, G. (1995). Proximity constraints and representable trees (extended abstract). In: Tamassia, R., Tollis, I.G. (eds) Graph Drawing. GD 1994. Lecture Notes in Computer Science, vol 894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58950-3_389
Download citation
DOI: https://doi.org/10.1007/3-540-58950-3_389
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58950-1
Online ISBN: 978-3-540-49155-2
eBook Packages: Springer Book Archive