On Bipartite Drawings and the Linear Arrangement Problem

Authors:
  • FSFarhad Shahrokhi
    Farhad Shahrokhi
  • OSOndrej Sýkora
    Ondrej Sýkora
  • LSLászló A. Székely
    László A. Székely
  • IVImrich Vrto
    Imrich Vrto
Publisher website
Google Scholar
Abstract
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(log 2 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(n 1.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.

This publication has 12 references indexed in Scilit: