Angle and Distance Constraints on Tree Drawings

Brandes, Ulrik and Schlieper, Barbara (2007) Angle and Distance Constraints on Tree Drawings. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006 , pp. 54-65(Official URL:

Full text not available from this repository.


We consider planar drawings of trees that must satisfy constraints on the angles between edges incident to a common vertex and on the distances between adjacent vertices. These requirements arise naturally in many applications such as drawing phylogenetic trees or route maps. For straight-line drawings, either class of constraints is always realizable, whereas their combination is not in general. We show that straight-line realizability can be tested in linear time, and give an algorithm that produces drawing satisfying both groups of constraints together in a model where edges are represented as polylines with at most two bends per edge or as continuously differentiable curves.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-70904-6_7
Classifications: M Methods > M.999 Others

Actions (login required)

View Item View Item