Line Crossing Minimization on Metro Maps

Bekos, Michael A. and Kaufmann, Michael and Potika, Katerina and Symvonis, Antonios (2008) Line Crossing Minimization on Metro Maps. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 231-242 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_24).

Full text not available from this repository.

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 line which connects them, whereas the paths illustrate the lines connecting terminal stations. We call this the metro-line crossing minimization problem (MLCM). In contrast to the problem of drawing the underlying graph nicely, MLCM has received fewer attention. It was recently introduced by Benkert et. al in [4]. In this paper, as a first step towards solving MLCM in arbitrary graphs, we study path and tree networks. We examine several variations of the problem for which we develop algorithms for obtaining optimal solutions.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_24
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:858

Repository Staff Only: item control page

References

M. Asquith, J. Gudmundsson, and D. Merrick. An ILP for the line ordering problem. Technical Report PA006288, National ICT Australia, 2007.

G. D. Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.

M. A. Bekos, M. Kaufmann, K. Potika, and A. Symvonis. Line crossing minimization on metro maps. Technical Report WSI-2007-03, University of Tübingen, 2007.

M. Benkert, M. Nöllenburg, T. Uno, and A. Wolff. Minimizing intra-edge crossings in wiring diagrams and public transport maps. In M. Kaufmann and D. Wagner, editors, Proc. 14th Int. Symposium on Graph Drawing (GD'06), volume 4372 of Lecture Notes in Computer Science, pages 270-281. Springer-Verlag, 2007.

S.-H. Hong, D. Merrick, and H. A. D. d. Nascimento. The metro map layout problem. In N. Churcher and C. Churcher, editors, Australasian Symposium on Information Visualisation, (invis.au'04), volume 35 of CRPIT, pages 91-100. ACS, 2004.

M. Kaufmann and D. Wagner, editors. Drawing Graphs: Methods and Models, volume 2025 of Lecture Notes in Computer Science. Springer-Verlag, 2001.

S. Masuda, K. Nakajima, T. Kashiwabara, and T. Fujisawa. Crossing minimization in linear embeddings of graphs. IEEE Trans. Comput., 39(1):124-127, 1990.

M. Nöllenburg and A. Wolff. A mixed-integer program for drawing high-quality metro maps. In P. Healy and N. S. Nikolov, editors, Proc. 13th Int. Symposium on Graph Drawing (GD'05), volume 3843 of Lecture Notes in Computer Science, pages 321-333. Springer-Verlag, 2006.

J. M. Stott and P. Rodgers. Metro map layout using multicriteria optimization. In Proc. 8th International Conference on Information Visualisation, pages 355-362. IEEE Computer Society, 2004.