The Complexity of Drawing Tree-Structured Diagrams

Kensei TSUCHIDA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.7   pp.901-908
Publication Date: 1995/07/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
graph drawing,  tree-structured diagrams,  NP-complete,  constraints for tree drawing,  

Full Text: PDF(562.4KB)>>
Buy this Article




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 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 diagrm is a tree with variably sized rectangular nodes. We consider the layout problem of tree-structured diagrams on Z2 (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. Furthermore, 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.