On embedding binary trees into hypercubes

It is conjectured that an N-vertex binary tree can be embedded into a inverted right perpendicular log N inverted left perpendicular-dimensional cube with a dilation of at most 2. Although it is known that an N-vertex binary tree can be embedded into a inverted right perpendicular log N inverted left perpendicular-dimensional cube with a dilation of at most 8, the conjecture has been verified only for some restricted classes of binary trees. This paper verifies the conjecture for wider classes of binary trees. That is, we show that a 2 "-vertex balanced one-legged caterpillar with leg length of at most 2 can be embedded into an n-dimensional cube with dilation 1, and that an N-vertex binary tree with proper pathwidth of at most 2 can be embedded into a inverted right perpendicular log N inverted left perpendicular-dimensional cube with dilation 2. (C) 1999 Scripta Technica.