@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",

}