Orthogonal hypergraph routing for improved visibility
Orthogonal hypergraph routing for improved visibility
复制标题
正交超图路由可提高可视性
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
B. Becker
中科院分区：
文献类型：
--
作者：
T. Eschbach;Wolfgang Günther;B. Becker
电路的可视化是电子设计自动化的一个重要研究领域。一种普遍接受的可视化电路的方法是将栅极与层对齐，并使用正交线连接栅极。在我们的模型中，我们假设在两个连续的层之间，每个网络只允许占用一个轨道。这避免了导线中不必要的弯曲，并有助于提高绘图的清晰度。然后应用交叉减少步骤以进一步提高电路原理图的可读性。首先，我们假设节点已经固定在一个分层超图结构上。我们考虑的问题，分配两个层之间的超边缘的轨道。这个想法是最小化超边交叉的总数。我们证明了寻找最优解是NP-困难的。然后，与许多其他方法相比，这些方法在放置所有节点之后路由所有布线，我们专注于一种新的方法，该方法动态地重新排序层内的节点，以进一步减少超边交叉的数量。一个有效的算法，提出了最大限度地减少超边交叉。实验结果表明，该算法在运行时间适中的情况下，可以显著提高绘图质量。
Visualization of circuits is an important research area in electronic design automation. One commonly accepted method to visualize a circuit aligns the gates to layers and uses orthogonal lines to connect the gates. In our model we assume that between two consecutive layers every net is allowed to occupy only one track. This avoids unnecessary bends in the wires and helps to improve the clarity of the drawing. Then a crossing reduction step is applied to further improve the readability of the circuit schematics. First we assume that the nodes have already been fixed on a layered hypergraph structure. We consider the problem of assigning the hyperedges between two layers to tracks. The idea is to minimize the total number of hyperedge crossings. We prove that finding the best solution is NP-hard. Then, in contrast to many other approaches which route all the wiring after placing all nodes we focus on a new approach which dynamically reorders the nodes within the layers to further reduce the number of hyperedge crossings. An efficient algorithm is presented that minimizes the hyperedge crossings. Experimental results are provided which show that the drawings can be improved significantly while the running time remains moderate.