On Bipartite Drawings and the Linear Arrangement Problem
On Bipartite Drawings and the Linear Arrangement Problem
复制标题
关于二分图和线性排列问题
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
I. Vrto
中科院分区：
文献类型：
--
作者：
F. Shahrokhi;O. Sýkora;L. Székely;I. Vrto
研究了二部交叉数问题，并建立了该问题与线性排列问题的联系。导出了最优交叉次数的下界和上界，其中主要项是最优排列值。给出了二部交叉数的两种多项式时间逼近算法。对于有n个顶点的大量二部图，性能保证分别是最优值的O（log n）和O（log2 n）倍。目前还没有一种多项式时间近似算法能产生一个可证明的好解。对于树，导出了用线性排列和度的最优值表示最优交叉数的公式，得到了计算二部交叉数的O（n1.6）时间算法。
The bipartite crossing number problem is studied and a connection between this problem and the linear arrangement problem is established. A lower bound and an upper bound for the optimal number of crossings are derived, where the main terms are the optimal arrangement values. Two polynomial time approximation algorithms for the bipartite crossing number are obtained. The performance guarantees are O(log n) and O(log2 n) times the optimal, respectively, for a large class of bipartite graphs on n vertices. No polynomial time approximation algorithm which could generate a provably good solution had been known. For a tree, a formula is derived that expresses the optimal number of crossings in terms of the optimal value of the linear arrangement and the degrees, resulting in an O(n1.6) time algorithm for computing the bipartite crossing number.
The problem of computing a maximum weight biplanar subgraph of an acyclic graph is also studied and a linear time algorithm for solving it is derived. No polynomial time algorithm for this problem was known, and the unweighted version of the problem had been known to be NP-hard, even for planar bipartite graphs of degree at most 3.