06059113

j

06059113 Kumamoto, Masao Miyano, Eiji Optimal distortion embedding of complete binary trees into lines. Inf. Process. Lett. 112, No. 10, 365-370 (2012). 2012 Elsevier Sciences Publishers (North-Holland), Amsterdam EN line embedding distortion complete binary tree optimal bound combinatorial problems Zbl 1191.68452

doi:10.1016/j.ipl.2012.02.003

Summary: We study the problem of embedding an unweighted complete binary tree into a line with low distortion. Very recently, {\it C. Mathieu} and {\it C. Papamanthou} [ibid. 108, No. 4, 175--178 (2008; Zbl 1191.68452)] showed that the inorder traversal of the complete binary tree of height $h$ gives a line embedding of distortion $O(2^{h})$, and conjectured that the current lower bound of $\Omega ( \frac{2^h}{h} )$ increases to $\Omega (2^{h})$, i.e., the upper bound of $O(2^{h})$ is best possible. In this paper, we disprove their conjecture by providing a line embedding of the complete binary tree of height $h$ with optimal distortion $\varTheta ( \frac{2^h}{h})$.