Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00122
Orthogonal Hypergraph Drawing for Improved Visibility
Vol. 10, no. 2, pp. 141-157, 2006. Regular paper.
Abstract 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.
|
Journal Supporters
|