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 B-drawings, first defined by Kirkpatrick and Radke in the context of computational morphology. Such proximity drawings include as special cases the well-known Gabriel, relative neighborhood and strip drawings. Complete characterizations of those trees that admit open B-drawings for 0 <= B <= 1/(1-cos(2pi/5)) and 1/cos(2pi/5) < B < infinity or closed B-drawings for 0 <= B < 1/(1-cos(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 B-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.
Descriptors : *GRAPHS, MATHEMATICAL MODELS, ALGORITHMS, LINEAR PROGRAMMING, ENGINEERING DRAWINGS, PLANE GEOMETRY.
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE