Geodesic
On Metro-Line Crossing Minimization
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Sixteenth International Symposium on Graph Drawing, GD 2008 , Tome 14 (2010) no. 1, pp. 75-96.

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

We consider the problem of drawing a set of simple paths along the edges of an embedded underlying graph G=(V,E) so that the total number of crossings among pairs of paths is minimized. This problem arises when drawing metro maps, where the embedding of G depicts the structure of the underlying network, the nodes of G correspond to train stations, an edge connecting two nodes implies that there exists a railway track connecting them, whereas the paths illustrate the metro lines connecting terminal stations. We call this the metro-line crossing minimization problem (MLCM). We examine several variations of the problem for which we develop algorithms that yield optimal solutions. 
@article{JGAA_2010_14_1_a4,
     author = {Evmorfia Argyriou and Michael Bekos and Michael Kaufmann and Antonios Symvonis},
     title = {On {Metro-Line} {Crossing} {Minimization}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {75--96},
     publisher = {mathdoc},
     volume = {14},
     number = {1},
     year = {2010},
     doi = {10.7155/jgaa.00199},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00199/}
}
TY  - JOUR
AU  - Evmorfia Argyriou
AU  - Michael Bekos
AU  - Michael Kaufmann
AU  - Antonios Symvonis
TI  - On Metro-Line Crossing Minimization
JO  - Journal of Graph Algorithms and Applications
PY  - 2010
SP  - 75
EP  - 96
VL  - 14
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00199/
DO  - 10.7155/jgaa.00199
LA  - en
ID  - JGAA_2010_14_1_a4
ER  - 
%0 Journal Article
%A Evmorfia Argyriou
%A Michael Bekos
%A Michael Kaufmann
%A Antonios Symvonis
%T On Metro-Line Crossing Minimization
%J Journal of Graph Algorithms and Applications
%D 2010
%P 75-96
%V 14
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00199/
%R 10.7155/jgaa.00199
%G en
%F JGAA_2010_14_1_a4
Evmorfia Argyriou; Michael Bekos; Michael Kaufmann; Antonios Symvonis. On Metro-Line Crossing Minimization. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Sixteenth International Symposium on Graph Drawing, GD 2008
					, Tome 14 (2010) no. 1, pp. 75-96. doi : 10.7155/jgaa.00199. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00199/

Cité par Sources :