Proximity Constraints and Representable Trees (extended abstract)

Bose, Prosenjit and Di Battista, Giuseppe and Lenhart, William J. and Liotta, Giuseppe (1995) Proximity Constraints and Representable Trees (extended abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 340-351(Official URL:

Full text not available from this repository.


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

Actions (login required)

View Item View Item