Improved Bounds for Drawing Trees on Fixed Points with LShaped EdgesBiedl, Therese and Chan, Timothy M. and Derka, Martin and Jain, Kshitij and Lubiw, Anna (2017) Improved Bounds for Drawing Trees on Fixed Points with LShaped Edges. In: Graph Drawing and Network Visualization. GD 2017, September 2527 , pp. 305317(Official URL: https://doi.org/10.1007/9783319739151_24). Full text not available from this repository.
Official URL: https://doi.org/10.1007/9783319739151_24
AbstractLet T be an nnode tree of maximum degree 4, and let P be a set of n points in the plane with no two points on the same horizontal or vertical line. It is an open question whether T always has a planar drawing on P such that each edge is drawn as an orthogonal path with one bend (an “Lshaped” edge). By giving new methods for drawing trees, we improve the bounds on the size of the point set P for which such drawings are possible to: O(n^1.55) for maximum degree 4 trees; O(n1.22) for maximum degree 3 (binary) trees; and O(n^1.142) for perfect binary trees. Drawing ordered trees with Lshaped edges is harder—we give an example that cannot be done and a bound of O(nlogn) points for Lshaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars.
Actions (login required)
