Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area

Abstract

Given a rooted binary tree T and a tuple (w, h), we wish to test whether there exists a strict upward drawing of T on a w × h grid; that is, a planar grid drawing with straight-line edges where every vertex has a strictly lower y-coordinate than its parent. Biedl and Mondal [2] prove that this problem is NP-hard for general trees; their construction crucially uses nodes of very high degree. Akatiya et al [1] prove that the problem is also NP-hard for binary trees with a fixed combinatorial embedding; their construction crucially relies on the fixed embedding. Both pose the question for binary trees and a free embedding as an open problem. Here, we show that this problem is also NP-hard.