The Complexity of Drawing Tree-Structured Diagrams

概要

論文の詳細を見る
Concerning the complexity of tree drawing, the following result of Supowit and Reingold is known : the problem of minimum drawing binary trees under several constraints is NP-complete. There remain, however, many open problems. For example, is it still NP-complete if we eliminate some constraints from the above set? In this paper, we treat tree-structured diagrams. A tree-structured diagram is a tree with variably sized rectangular nodes. We consider the layout problem of tree-structured diagrams on Z^2 (the integral lattice). Our problems are different from that of Supowit and Reingold, even if our problems are limited to binary trees. In fact, our set of constraints and that of Supowit and Reingold are incomparable. We show that a problem is NP-complete under a certain set of constraints. Further-more, we also show that another problem is still NP-complete, even if we delete a constraint concerning with the symmetry from the previous set of constraints. This constraint corresponds to one of the constraints of Supowit and Reingold, if the problem is limited to binary trees.
社団法人電子情報通信学会の論文
1995-07-25