Geodesic
Ordering Metro Lines by Block Crossings
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 111-153.

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

A problem that arises in drawings of transportation networks is to minimize the number of crossings between different transportation lines. While this can be done efficiently under specific constraints, not all solutions are visually equivalent. We suggest merging single crossings into block crossings, that is, crossings of two neighboring groups of consecutive lines. Unfortunately, minimizing the total number of block crossings is NP-hard even for very simple graphs. We give approximation algorithms for special classes of graphs and an asymptotically worst-case optimal algorithm for block crossings on general graphs. Furthermore, we show that the problem remains NP-hard on planar graphs even if both the maximum degree and the number of lines per edge are bounded by constants; on trees, this restricted version becomes tractable.
DOI : 10.7155/jgaa.00351
Keywords: metro-line crossing minimization, metro maps, crossing minimization, sorting permutations, sorting by transpositions, edge bundling 
@article{JGAA_2015_19_1_a5,
     author = {Martin Fink and Sergey Pupyrev and Alexander Wolff},
     title = {Ordering {Metro} {Lines} by {Block} {Crossings}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {111--153},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00351},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00351/}
}
TY  - JOUR
AU  - Martin Fink
AU  - Sergey Pupyrev
AU  - Alexander Wolff
TI  - Ordering Metro Lines by Block Crossings
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 111
EP  - 153
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00351/
DO  - 10.7155/jgaa.00351
LA  - en
ID  - JGAA_2015_19_1_a5
ER  - 
%0 Journal Article
%A Martin Fink
%A Sergey Pupyrev
%A Alexander Wolff
%T Ordering Metro Lines by Block Crossings
%J Journal of Graph Algorithms and Applications
%D 2015
%P 111-153
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00351/
%R 10.7155/jgaa.00351
%G en
%F JGAA_2015_19_1_a5
Martin Fink; Sergey Pupyrev; Alexander Wolff. Ordering Metro Lines by Block Crossings. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 111-153. doi : 10.7155/jgaa.00351. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00351/

Cité par Sources :