Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the Sixteenth International Symposium on Graph Drawing, GD 2008
DOI: 10.7155/jgaa.00199
On Metro-Line Crossing Minimization
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.
Submitted: November 2008.
Reviewed: July 2009.
Revised: August 2009.
Accepted: November 2009.
Final: December 2009.
Published: January 2010.
Communicated by Maurizio Patrignani and Ioannis G. Tollis
article (PDF)
BibTeX