Crossing Reduction by Windows Optimization
Crossing Reduction by Windows Optimization
复制标题
通过 Windows 优化减少交叉
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
B. Becker
中科院分区：
文献类型：
--
作者：
T. Eschbach;Wolfgang Günther;R. Drechsler;B. Becker
边交叉数是衡量图形可读性的一个常用指标。本文提出了一种新的高质量多层直线交叉最小化算法。所提出的方法使用了局部优化技术，其中节点和边缘的子集被精确地处理。该算法使用的方式，类似于在逻辑电路的形式验证领域中使用的窗口上的优化。与大多数现有的分层方法相比，同时考虑两个以上的层。该算法尝试基于节点的初始放置来减少交叉的总数，并且因此也可以在后处理步骤中使用。实验证明所提出的技术在基准电路设计领域的有效性。
The number of edge crossings is a commonly accepted measure to judge the readability of graph drawings. In this paper we present a new algorithm for high quality multi-layer straight-line crossing minimization. The proposed method uses a local optimization technique where subsets of nodes and edges are processed exactly. The algorithm uses optimization on a window applied in a manner, similar to those used in the area of formal verification of logic circuits. In contrast to most existing heuristics, more than two layers are considered simultaneously. The algorithm tries to reduce the total number of crossings based on an initial placement of the nodes and can thus also be used in a post-processing step. Experiments are given to demonstrate the efficacy of the proposed technique on benchmarks from the area of circuit design.