Computing crossing numbers in quadratic time
Computing crossing numbers in quadratic time
复制标题
DOI：
10.1145/380752.380805
复制
发表时间：
2000-09
期刊：
影响因子：
--
通讯作者：
Martin Grohe
中科院分区：
文献类型：
--
作者：
Martin Grohe
我们表明，对于每一个固定的k\ge 0有一个二次时间算法，决定是否一个给定的图有交叉数最多为k，如果是这种情况下，计算绘图的图形在平面上最多为k个交叉。
We show that for every fixed k\ge 0 there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, computes a drawing of the graph in the plane with at most k crossings.