TY - GEN

T1 - Improved bounds for drawing trees on fixed points with L-Shaped edges

AU - Biedl, Therese

AU - Chan, Timothy M.

AU - Derka, Martin

AU - Jain, Kshitij

AU - Lubiw, Anna

N1 - Publisher Copyright:
© Springer International Publishing AG 2018.

PY - 2018

Y1 - 2018

N2 - 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(n1.55) for maximum degree 4 trees; O(n1.22) for maximum degree 3 (binary) trees; and O(n1.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.

AB - 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(n1.55) for maximum degree 4 trees; O(n1.22) for maximum degree 3 (binary) trees; and O(n1.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.

UR - http://www.scopus.com/inward/record.url?scp=85041848404&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85041848404&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-73915-1_24

DO - 10.1007/978-3-319-73915-1_24

M3 - Conference contribution

AN - SCOPUS:85041848404

SN - 9783319739144

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 305

EP - 317

BT - Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers

A2 - Ma, Kwan-Liu

A2 - Frati, Fabrizio

PB - Springer

T2 - 25th International Symposium on Graph Drawing and Network Visualization, GD 2017

Y2 - 25 September 2017 through 27 September 2017

ER -