
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

The Complexity of Drawing TreeStructured Diagrams
Kensei TSUCHIDA
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E78D
No.7
pp.901908 Publication Date: 1995/07/25
Online ISSN:
DOI:
Print ISSN: 09168532 Type of Manuscript: PAPER Category: Algorithm and Computational Complexity Keyword: graph drawing, treestructured diagrams, NPcomplete, constraints for tree drawing,
Full Text: PDF>>
Summary:
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 NPcomplete. There remain, however, many open problems. For example, is it still NPcomplete if we eliminate some constraints from the above set? In this paper, we treat treestructured diagrams. A treestructured diagrm is a tree with variably sized rectangular nodes. We consider the layout problem of treestructured 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 NPcomplete under a certain set of constraints. Furthermore, we also show that another problem is still NPcomplete, 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.

