An Approximation Algorithm for the Two-Layered Graph Drawing Problem
An Approximation Algorithm for the Two-Layered Graph Drawing Problem
复制标题
两层绘图问题的近似算法
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
A. Sugimoto
中科院分区：
文献类型：
--
作者：
Atsuko Yamaguchi;A. Sugimoto
我们提出了一种用于两层图的最小边交叉问题的多项式时间近似算法。我们展示了算法的近似率与输入图下层顶点的最大度之间的关系。当最大次数不大于4时，近似比率为2，并且随着最大次数变大，该比率单调增加到3。我们还展示了我们的实验，表明我们的算法对于稠密图和稀疏图构建了比重心法和中值法更好的解决方案。
We present a polynomial-time approximation algorithm for the minimum edge crossings problem for two-layered graphs. We show the relationship between the approximation ratio of our algorithm and the maximum degree of the vertices in the lower layer of the input graph. When the maximum degree is not greater than four, the approximation ratio is two and this ratio monotonically increases to three as the maximum degree becomes larger. We also present our experiments, showing that our algorithm constructs better solutions than the barycenter method and the median method for dense graphs as well as sparse graphs.