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.

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
ID Code:761

Repository Staff Only: item control page

References

C. Bachmaier, U. Brandes, and B. Schlieper. Drawing phylogenetic trees. In Proc. 16th Intl. Symp. Algorithms and Computation (ISAAC '05), volume 3827 of LNCS, pages 1110-1121. Springer, 2005.

U. Brandes, G. Shubina, and R. Tamassia. Improving angular resolution in visualizations of geographic networks. In Data Visualization: Proc. 2nd Joint EUROGRAPHICS and IEEE TCVG Symp. Visualization, VisSym, pages 23-33. Springer, 29-30 2000.

B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6(5):485-524, 1991.

C. C. Cheng, C. A. Duncan, M. T. Goodrich, and S. G. Kobourov. Drawing planar graphs with circular arcs. In Proc. Graph Drawing 1999, volume 1731 of LNCS, pages 117-126. Springer, 1999.

P. Eades and N. C. Wormald. Fixed edge-length graph drawing is NP-hard. Discrete Applied Mathematics, 28:111-134, 1990.

B. Finkel and R. Tamassia. Curvilinear Graph Drawing Using the Force-Directed Method. In Proc. Graph Drawing 2004, volume 3383 of LNCS, pages 448-453. Springer, 2004.

A. Garg. On drawing angle graphs. In Proc. Graph Drawing 1994, volume 894 of LNCS, pages 84-95. Springer, 1994.

M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

G. Melancon and I. Hermann. Circular drawing of rooted trees. Technical report 9817, Reports of the Center for Mathematics and Computer Science, 1998.

J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. In Proc. Graph Drawing 1998, volume 1547 of LNCS, pages 263-274. Springer, 1998.