Your single point of reference for all your Geotechnical Inquiries
AN IMPROVED ALGORITHM FOR THE METRO-LINE CROSSING MINIMIZATION PROBLEM (2010)
In the metro-line crossing minimization problem, we are given a plane graph G = (V,E) and a set L of simple paths (or lines) that cover G, that is, every edge e ϵ E belongs to at least one path in L. The problem is to draw all paths in L along the edges of G such that the number of crossings between paths is minimized. This crossing minimization problem arises, for example, when drawing metro maps, in which multiple transport lines share parts of their routes.
We present a new line-layout algorithm with O (│L│2·│V│) running time that improves the best previous algorithms for two variants of the metro-line crossing minimization problem in unrestricted plane graphs.
Graph Drawing, Lecture Notes in Computer Science Volume 5849, 2010, pp 381-392
Fakultät für Informatik, Universität Karlsruhe (TH) and Karlsruhe Institute of Technology (KIT), Karlsruhe