Improved Upper And Lower Bounds For Lr Drawings Of Binary Trees
April 23, 2021 - Chan, T.M.; Zhengcheng Huang
Print
EmailJournal or Book Title: Graph Drawing and Network Visualization. 28th International Symposium, GD 2020. Revised Selected Papers. Lecture Notes in Computer Science (LNCS 12590)
Volume/Issue:
Year Published: 2020
In SODA99, Chan introduced a simple type of planar straight-line upward order-preserving drawings of binary trees, known asLRdrawings: such a drawing is obtained by picking a root-to-leaf path, drawing the path as a straight line, and recursively drawing the subtrees along the paths. Chan proved that any binary tree withnnodes admits an LR drawing with O(n0.48) width. In SODA17, Frati, Patrignani, and Roselli proved that there exist families ofn-node binary trees for which any LR drawing has Omega(n0.418) width. In this paper, we improve Chans upper bound to O(n0.437) and Fratietal.s lower bound to Omega(n0.429).
DOI: 10.1007/978-3-030-68766-3_6
Type of Publication: Conference Paper