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. 340351(Official URL: http://dx.doi.org/10.1007/3540589503_389). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_389
AbstractA family of proximity drawings of graphs called open and closed \betadrawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete characterizations of which trees admit open \betadrawings for 0 \leq \beta \leq \frac{1}{2 sin^2(\pi/5)} and \frac{1}{cos(2\pi/5)} < \beta < \infty or closed \betadrawings0 \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 \betadrawing, 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.
Actions (login required)
