
Accession Number : ADA318674
Title : Proximity Constraints and Representable Trees,
Descriptive Note : Technical rept.,
Corporate Author : BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE
Personal Author(s) : Bose, Prosenjit ; Di Battista, Giuseppe ; Lenhart, William ; Liotta, Giuseppe
PDF Url : ADA318674
Report Date : 1996
Pagination or Media Count : 30
Abstract : This paper examines an infinite family of proximity drawings of graphs called open and closed Bdrawings, first defined by Kirkpatrick and Radke in the context of computational morphology. Such proximity drawings include as special cases the wellknown Gabriel, relative neighborhood and strip drawings. Complete characterizations of those trees that admit open Bdrawings for 0 <= B <= 1/(1cos(2pi/5)) and 1/cos(2pi/5) < B < infinity or closed Bdrawings for 0 <= B < 1/(1cos(2pi/5)) and 1/cos(2pi/5) <= B <= infinity are given, as well as partial characterizations for other values of B. For the intervals of B in which complete characterizations are given, it can be determined in linear time whether a tree admits an open or closed Bdrawing, 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.
Descriptors : *GRAPHS, MATHEMATICAL MODELS, ALGORITHMS, LINEAR PROGRAMMING, ENGINEERING DRAWINGS, PLANE GEOMETRY.
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE