1-1hit |
It has been known that an N-vertex binary tree can be embedded into the path and grid with dilation O(N/logN) and O((N/logN)), respectively. This paper shows that an N-vertex binary tree with proper pathwidth at most k can be embedded into the path grid with dilation O(N/N1/k) and O((N/N1/2k)), respectively.