Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps

Benkert, Marc and Nöllenburg, Martin and Uno, Takeaki and Wolff, Alexander (2007) Minimizing Intra-Edge Crossings in Wiring Diagrams and Public Transport Maps. In: Graph Drawing 14th International Symposium, GD 2006, September 18-20, 2006, Karlsruhe, Germany , pp. 270-281 (Official URL: http://dx.doi.org/10.1007/978-3-540-70904-6_27).

Full text not available from this repository.

Abstract

In this paper we consider a new problem that occurs when drawing wiring diagrams or public transportation networks. Given an embedded graph G=(V,E) (e.g., the streets served by a bus network) and a set L of paths in G (e.g., the bus lines), we want to draw the paths along the edges of G such that they cross each other as few times as possible. For esthetic reasons we insist that the relative order of the paths that traverse a node does not change within the area occupied by that node. Our main contribution is an algorithm that minimizes the number of crossings on a single edge {u,v} in E if we are given the order of the incoming and outgoing paths. The difficulty is deciding the order of the paths that terminate in u or v with respect to the fixed order of the paths that do not end there. Our algorithm uses dynamic programming and takes O(n^2) time, where n is the number of terminating paths.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-70904-6_27
Classifications:G Algorithms and Complexity > G.420 Crossings
P Styles > P.600 Poly-line
ID Code:782

Repository Staff Only: item control page

References

P. F. Cortese, G. D. Battista, M. Patrignani, and M. Pizzonia. On embedding a cycle in a plane graph. In P. Healy and N. S. Nikolov, editors, Proc. 13th Int. Symp. Graph Drawing (GD'05), volume 3843 of LNCS, pages 49-60. Springer-Verlag, 2006.

R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis. Cambridge University Press, 1998.

M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Alg. Disc. Meth., 4:312-316, 1983.

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. Symp. Graph Drawing (GD'05), volume 3843 of LNCS, pages 321-333. Springer-Verlag, 2006.