An Improved Algorithm for the Metro-line Crossing Minimization Problem
An Improved Algorithm for the Metro-line Crossing Minimization Problem
复制标题
地铁线路交叉最小化问题的改进算法
DOI：
10.1007/978-3-642-11805-0_36
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Nöllenburg
中科院分区：
文献类型：
--
作者：
M. Nöllenburg
在地铁线路交叉最小化问题中，我们给出一个平面图G=（V，E）和一个覆盖G的简单路（或线）集合$\mathcal{L}$，即E中的每条边e至少属于$\mathcal{L}$中的一条路。问题是沿着G的边绘制$\mathcal{L}$沿着的所有路径，使得路径之间的交叉数最小。例如，当绘制地铁地图时，多条交通线路共享其部分路线时，就会出现这种交叉最小化问题。
我们提出了一个新的线布局算法，$O（|\mathcal{L}|^2\cdot| V|）$运行时间，改进了以前最好的算法的两个变种的地铁线交叉最小化问题的无限制平面图。对于第一种变体，其中所谓的外围条件成立并且在输入中给出末端侧分配，阿斯奎斯等人[1]给出了$O（|\mathcal{L}|^3\cdot| E| ^{2.5}）$时间算法。对于第二个变体，其中所有的线都是G的1度顶点之间的路，Argyriou等人[2]给出了一个O（（|E| +|\mathcal{L}|^2）\cdot| E|）$时间算法。
In the metro-line crossing minimization problem, we are given a plane graph G=(V,E) and a set $\mathcal{L}$ of simple paths (or lines) that coverG, that is, every edge e∈E belongs to at least one path in $\mathcal{L}$. The problem is to draw all paths in $\mathcal{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(|\mathcal{L}|^2\cdot |V|)$ running time that improves the best previous algorithms for two variants of the metro-line crossing minimization problem in unrestricted plane graphs. For the first variant, in which the so-called periphery condition holds and terminus side assignments are given in the input, Asquith et al. [1] gave an $O(|\mathcal{L}|^3\cdot |E|^{2.5})$-time algorithm. For the second variant, in which all lines are paths between degree-1 vertices of G, Argyriou et al. [2] gave an $O((|E|+|\mathcal{L}|^2)\cdot |E|)$-time algorithm.