An Improved Algorithm for the Metroline Crossing Minimization ProblemNöllenburg, Martin (2010) An Improved Algorithm for the Metroline Crossing Minimization Problem. In: Graph Drawing 17th International Symposium, GD 2009, September 2225, 2009 , pp. 381392(Official URL: http://dx.doi.org/10.1007/9783642118050_36). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642118050_36
AbstractIn the metroline 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 linelayout algorithm with O(L2 · V ) running time that improves the best previous algorithms for two variants of the metroline crossing minimization problem in unrestricted plane graphs. For the ﬁrst variant, in which the socalled periphery condition holds and terminus side assignments are given in the input, Asquith et al. [1] gave an O(L3 · E2.5 )time algorithm. For the second variant, in which all lines are paths between degree1 vertices of G, Argyriou et al. [2] gave an O((E + L2 ) · E)time algorithm.
Actions (login required)
