Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges

2017/09/05 by Biedl, Therese, Chan, Timothy M., Derka, Martin +2
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1709.01456

Abstract

Let T be an n-node 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 "L-shaped" 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(n^1.22) for maximum degree 3 (binary) trees; and O(n^1.142) for perfect binary trees. Drawing ordered trees with L-shaped edges is harder---we give an example that cannot be done and a bound of O(n log n) points for L-shaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars.

Related

• On L-shaped point set embeddings of trees: first non-embeddable examples
• Improved Upper and Lower Bounds for LR Drawings of Binary Trees
• Tree Drawings Revisited
• Order-preserving drawings of trees with approximately optimal height (and small width)
• Low Ply Drawings of Trees and 2-Trees