Geodesic
Simple and Efficient Bilayer Cross Counting
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002 , Tome 8 (2004) no. 2, pp. 179-194.

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

We consider the problem of counting the interior edge crossings when a bipartite graph G=(V,E) with node set V and edge set E is drawn such that the nodes of the two shores of the bipartition are drawn as distinct points on two parallel lines and the edges as straight line segments. The efficient solution of this problem is important in layered graph drawing. Our main observation is that it can be reduced to counting the inversions of a certain sequence. This leads directly to an O(|E|log|V|) algorithm based on merge sorting. We present an even simpler O(|E|log|Vsmall|) algorithm, where Vsmall is the smaller cardinality node set in the bipartition of the node set V of the graph. This algorithm is very easy to implement. Our computational experiments on a large collection of instances show that it performs well in comparison to previously published algorithms, which are much more complicated to understand and implement.
DOI : 10.7155/jgaa.00088
Keywords: rotation distance, higher valence trees 
@article{JGAA_2004_8_2_a3,
     author = {Wilhelm Barth and Petra Mutzel and Michael J\"unger},
     title = {Simple and {Efficient} {Bilayer} {Cross} {Counting}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {179--194},
     publisher = {mathdoc},
     volume = {8},
     number = {2},
     year = {2004},
     doi = {10.7155/jgaa.00088},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00088/}
}
TY  - JOUR
AU  - Wilhelm Barth
AU  - Petra Mutzel
AU  - Michael Jünger
TI  - Simple and Efficient Bilayer Cross Counting
JO  - Journal of Graph Algorithms and Applications
PY  - 2004
SP  - 179
EP  - 194
VL  - 8
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00088/
DO  - 10.7155/jgaa.00088
LA  - en
ID  - JGAA_2004_8_2_a3
ER  - 
%0 Journal Article
%A Wilhelm Barth
%A Petra Mutzel
%A Michael Jünger
%T Simple and Efficient Bilayer Cross Counting
%J Journal of Graph Algorithms and Applications
%D 2004
%P 179-194
%V 8
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00088/
%R 10.7155/jgaa.00088
%G en
%F JGAA_2004_8_2_a3
Wilhelm Barth; Petra Mutzel; Michael Jünger. Simple and Efficient Bilayer Cross Counting. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Symposium on Graph Drawing, GD 2002
					, Tome 8 (2004) no. 2, pp. 179-194. doi : 10.7155/jgaa.00088. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00088/

Cité par Sources :