Geodesic
Orthogonal Hypergraph Drawing for Improved Visibility
Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 141-157.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00122
Keywords: hypergraph drawing, crossings, orthogonal drawing, circuit schematic drawing 
@article{JGAA_2006_10_2_a2,
     author = {Thomas Eschbach and Wolfgang Guenther and Bernd Becker},
     title = {Orthogonal {Hypergraph} {Drawing} for {Improved} {Visibility}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {141--157},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2006},
     doi = {10.7155/jgaa.00122},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00122/}
}
TY  - JOUR
AU  - Thomas Eschbach
AU  - Wolfgang Guenther
AU  - Bernd Becker
TI  - Orthogonal Hypergraph Drawing for Improved Visibility
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 141
EP  - 157
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00122/
DO  - 10.7155/jgaa.00122
LA  - en
ID  - JGAA_2006_10_2_a2
ER  - 
%0 Journal Article
%A Thomas Eschbach
%A Wolfgang Guenther
%A Bernd Becker
%T Orthogonal Hypergraph Drawing for Improved Visibility
%J Journal of Graph Algorithms and Applications
%D 2006
%P 141-157
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00122/
%R 10.7155/jgaa.00122
%G en
%F JGAA_2006_10_2_a2
Thomas Eschbach; Wolfgang Guenther; Bernd Becker. Orthogonal Hypergraph Drawing for Improved Visibility. Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 141-157. doi : 10.7155/jgaa.00122. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00122/

Cité par Sources :