The complexity of drawing trees nicely |
| |
Authors: | Kenneth J Supowit Edward M Reingold |
| |
Affiliation: | (1) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, Illinois, USA;(2) Present address: Hewlett-Packard, Computer Research Lab, 94304 Palo Alto, CA, USA |
| |
Abstract: | Summary We investigate the complexity of producing aesthetically pleasing drawings of binary trees, drawings that are as narrow as possible. The notion of what is aesthetically pleasing is embodied in several constraints on the placement of nodes, relative to other nodes. Among the results we give are: (1) There is no obvious principle of optimality that can be applied, since globally narrow, aesthetic placements of trees may require wider than necessary subtrees. (2) A previously suggested heuristic can produce drawings on n-node trees that are (n) times as wide as necessary. (3) The problem can be reduced in polynomial time to linear programming; hence, if the coordinates assigned to the nodes are continuous variables, then the problem can be solved in polynomial time. (4) If the placement is restricted to the integral lattice then the problem is NP-hard, as is its approximation to within a factor of about 4 per cent.This research was supported in part by the National Science Foundation, grant numbers NSF MCS 77-22830, NSF MCS 79-04897, and NSF MCS 81-17364 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|