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, Karlsruhe, Germany , pp. 54-65 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_7).
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.
Repository Staff Only: item control page