Accession Number:

ADA318674

Title:

Proximity Constraints and Representable Trees,

Descriptive Note:

Technical rept.,

Corporate Author:

BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE

Report Date:

1996-01-01

Pagination or Media Count:

30.0

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 11-cos2pi5 and 1cos2pi5 B infinity or closed B-drawings for 0 B 11-cos2pi5 and 1cos2pi5 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.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE