A family of proximity drawings of graphs called open and closed β-drawings, first defined in [15], and including the Gabriel, relative neighborhood and strip drawings, are investigated. Complete characterizations of which trees admit open β-drawings for or closed β-drawings for are given, as well as partial characterizations for other values of β. For β < ∞ in the intervals in which complete characterizations are given, it can be determined in linear time whether a tree admits an open or closed β-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.

Lecture Notes in Computer Science
School of Computer Science

Bose, P, Di Battista, G. (Giuseppe), Lenhart, W. (William), & Liotta, G. (Giuseppe). (1995). Proximity constraints and representable trees. In Lecture Notes in Computer Science. doi:10.1007/3-540-58950-3_389