@inproceedings{2950021aed72405880ca6a795464a545,
title = "Improved bounds for drawing trees on fixed points with L-Shaped edges",
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(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.",
author = "Therese Biedl and Chan, {Timothy M.} and Martin Derka and Kshitij Jain and Anna Lubiw",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2018. Copyright: Copyright 2018 Elsevier B.V., All rights reserved.; 25th International Symposium on Graph Drawing and Network Visualization, GD 2017 ; Conference date: 25-09-2017 Through 27-09-2017",
year = "2018",
doi = "10.1007/978-3-319-73915-1_24",
language = "English (US)",
isbn = "9783319739144",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag Berlin Heidelberg",
pages = "305--317",
editor = "Kwan-Liu Ma and Fabrizio Frati",
booktitle = "Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers",
}