Unit-length embedding of binary trees on a square grid - Gregori, Angelo (Information Processing Letters, 1989)
We give a proof of the fact that determining whether or not a given binary tree has a grid embedding with edges of unit length is an NP-complete problem. The proof follows an idea indicated by Bhatt and Cosmadakis in [1], which has been implemented using a new building block called U-tree.