Complexity dichotomy on partial grid recognition

Vinícius G. P. de Sá, Guilherme D. da Fonseca, Raphael Machado +1

Deciding whether a graph can be embedded in a grid using only unit-length edges is NP-complete, even when restricted to binary trees. However, it is not difficult to devise a numbe…