## Proximity Constraints and Representable Trees (extended abstract)
Bose, Prosenjit and Di Battista, Giuseppe and Lenhart, William J. and Liotta, Giuseppe
(1995)
Full text not available from this repository. ## AbstractA 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.
Repository Staff Only: item control page References |