Technical Report No. 192 - Abstract

Thomas Eschbach, Wolfgang Günther, Bernd Becker
Orthogonal Hypergraph Routing for Improved Visibility

Visualization of hypergraphs is an important research area in electronic design and automation. One commonly accepted method to visualize a circuit places all gates in several layers and then routes the wires in an orthogonal way between the layers. Our approach introduces the restriction that every net is allowed to occupy only one track. This avoids unnecessary bends in the wires and helps to improve the clarity of the drawn circuit. Then a crossing reduction step is applied to further improve the readability of the circuit schematics. Assume that some elements have already been fixed on a layered graph structure. In this paper, we consider the problem of assigning the hyperedges between two layers to tracks to minimize the total number of hyperedge crossings. First, we prove that solving this problem optimally is NP-hard. Then, we present a new heuristic to reduce the number of crossings. Finally, some promising experimental results on real circuits are given. The results show that in the majority of cases, the outcome of our algorithm are within 3% of the optimum solution.