一种基于继承次序与相关度的布图算法

Hierarchical layout algorithm based on order of succession and degree of association

在层次图边交叉最小化问题上,常规启发算法或者时间复杂度大或者布图效果不佳。基于Sugiyama布图算法模式,提出了一种交叉数减少算法,并从布局与布线两个主要方面介绍了其实现过程。两层图上的实验表明,该算法具有较好的性能,一定程度上克服了时间复杂度与效果的矛盾。

On the issue of crossing minimization, either time complexity or result of the conventional heuristic algorithm is unsatisfactory. The authors proposed a kind of cross-reduction algorithm based on Sugiyama algorithm, and introduced the implementation mainly in layout and routing. Experimental results of two-layer hierarchical graph show that the algorithm has better performance, to a certain extent, and overcomes the contradiction between time complexity and effect.