<p>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 ...