Two-Layer Planarization: Improving on Parameterized Algorithmics
Two-Layer Planarization: Improving on Parameterized Algorithmics
复制标题
两层平坦化：参数化算法的改进
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
H. Fernau
中科院分区：
文献类型：
--
作者：
H. Fernau
一个二分图是双平面的，如果顶点可以放在平面中的两条平行线上，使得当边被画成直线段时没有边交叉。我们研究了两个问题：2-Layer Planarization：可以从一个给定的图G中删除k条边，使剩下的图是双平面的吗？
1-层平面化：同样的问题，但一个层上的顶点的顺序是固定的。
改进Dujmovic等人的早期工作。[4]，我们解决了$mathcal{O}（k^{2}cdot 5.1926^{k} +| G|）$mathcal{O}（k^{3} cdot 2.5616^{k} +中的$时间和1层平面化问题|G| ^{2}）$时间。此外，我们推导出一个小的问题核的1层平面化。
A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that there are no edge crossings when edges are drawn as straight-line segments. We study two problems:2-Layer Planarization: can k edges be deleted from a given graph G so that the remaining graph is biplanar?
1-Layer Planarization: same question, but the order of the vertices on one layer is fixed.
Improving on earlier works of Dujmovic et al. [4], we solve the 2-Layer Planarization problem in $mathcal{O}(k^{2}cdot 5.1926^{k} +|G|)$ time and the 1-Layer Planarization problem in $mathcal{O}(k^{3} cdot 2.5616^{k} + |G|^{2})$ time. Moreover, we derive a small problem kernel for 1-Layer Planarization.