The complexity of drawing trees nicely
The complexity of drawing trees nicely
复制标题
漂亮地画树的复杂性
作者：
K. Supowit;E. Reingold
摘要我们调查了生成美观的二叉树图形的复杂性，这些图形尽可能地窄。什么是美观的概念体现在对节点相对于其他节点的放置的几个限制中。我们给出的结果包括：(1)没有明显的“最优原则”可以应用，因为全局狭窄的、美学的树木放置可能需要比必要的子树更宽的子树。(2)以前提出的启发式算法可以在n节点树上生成宽度为所需宽度的Θ(N)倍的图。(3)该问题可以在多项式时间内归结为线性规划问题，因此，如果分配给节点的坐标是连续变量，则该问题可以在多项式时间内求解。(4)如果布局被限制在整数格上，则问题是NP-难的，因为它的近似在大约4%的因子内。
SummaryWe 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.