节点图形布局算法

Question

依次向集合A中增加一个节点，每个节点按加入的顺序进行编号：1,2,3..N 除第一个节点外，每个节点都有且只有一个父节点. 注意：节点x， 其父节点只能是小于x的某个节点

现需要将这些节点及其父子关系(节点间连线)尽量展现在一张给定大小的图上, 并且节点之间连线条不能有交叉; 当给定大小的图实在无法显示时，允许对图进行适当的扩大.

请给出相关的数据结构和算法.

我初步的思路是：为了简化问题，将节点和连线均按方格显示，不处理斜线.

1. 首先从(0,0)开始放置第1个节点

2. 后续按右->下->左->上 顺序针的顺序查找周围是否有空(没有节点和连线且不超过边界)， 如果有空的话，就填进去。

3. 否则，没有超过边界的情况下，试着向右边扩展(也是按右->下->左->上进行尝试)，将右边的节点或线条及其相关的所有节点都右移动一格, 再把该节点放进去。

4. 如果第3步依然不能找到空位则按优先右扩，然后下扩的顺序对图进行扩充一列（或一行）

5. 另外，如果一个节点有多子节点，则也是按右->下->左->上 的顺序放置其子节点. 并且当子节点书多于3个时，对线条进行合并

例如：

假设初始图大小为4*4， 每个节点x的父节点都是x-1, 则排列如图一.
这时在加入17号节点时，由于没有空位，根据第4步则需要右扩一列，此时4，5，6，7右移一格，并在原3号位上增加一个空节点表示3和4的连接关系. 排列如图二。 这时在加入18，19号节点时，则可向下排列。
此时在加入20号节点后则如图三所示。

多个子节点的情况，假设3号节点增加了17，18，19，20号子节点，则如图四，五，六所示。

由于可能的情况比较多，不知道上面的步骤是否考虑到了所有的细节, 另外数据结构我也还没有想的很清楚，或者大家有更好的算法可以帮忙提供下，谢谢.

Answer 1

用方格法是不是反而使问题更复杂了？用下面的办法会不会更简单：

1. 首先把图看成是无向的，选择一个能使整个图的层级最少的根节点。

2. 确定根节点后，从上到下，从左到右，逐层顺序排布节点。如果本层a在b的左边，则下一层a的孩子也在b的孩子的左边。

3. 最后用直线连接父子节点，可以加上箭头。第二步的排列方式保证了本步不会产生交叉的连线。

上图中，选择节点3为画图的根，因为它只产生4层节点。如果用1则产生6层。