Given a tree T, we need to map the vertex in T to a point (i,j) in the grid graph. And we want the edges don't cross over and minimize the sum of the edges' length.
Some only property I got is the degree of vertex v in T is no greater than 4.
Is it a NP-complete problem? Or there exists an algorithm that I don't know.