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: http://dx.doi.org/10.1007/978-3-540-70904-6_7).

Full text not available from this repository.

Abstract

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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/761

Actions (login required)

View Item