Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00199 On Metro-Line Crossing Minimization Evmorfia Argyriou , Michael A. Bekos , Michael Kaufmann , and Antonios Symvonis Vol. 14, no. 1, pp. 75-96, 2010. Regular paper Abstract 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.
|
Accepted: November 2009. Published: January 2010. Final: December 2009. Revised: August 2009. Submitted: November 2008. Reviewed: July 2009. Communicated by Maurizio Patrignani and Ioannis Tollis |
| Journal of Graph Algorithms and Applications |