Low Ply Drawings of Trees

Angelini, Patrizio and Bekos, Michael A. and Bruckdorfer, Till and Hančl Jr., Jaroslav and Kaufmann, Michael and Kobourov, Stephen G. and Symvonis, Antonios and Valtr, Pavel (2016) Low Ply Drawings of Trees. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 236-248(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_19).

Full text not available from this repository.


We consider the recently introduced model of low ply graph drawing, in which the ply-disks of the vertices do not have many common overlaps, which results in a good distribution of the vertices in the plane. The ply-disk of a vertex in a straight-line drawing is the disk centered at it whose radius is half the length of its longest incident edge. The largest number of ply-disks having a common overlap is called the ply-number of the drawing. We focus on trees. We first consider drawings of trees with constant ply-number, proving that they may require exponential area, even for stars, and that they may not even exist for bounded-degree trees. Then, we turn our attention to drawings with logarithmic ply-number and show that trees with maximum degree 6 always admit such drawings in polynomial area.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.560 Geometry
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1546

Actions (login required)

View Item View Item