On bipartite drawings and the linear arrangement problem

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 app...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2001-01, Vol.30 (6), p.1773-1789
Main Authors: SHAHROKHI, Farhad, SYKORA, Ondrej, SZEKELY, Laszlo A, VRTO, Imrich
Format: Article
Language:English
Subjects:
Algorithms
Applied mathematics
Applied sciences
Approximation
Combinatorics
Combinatorics. Ordered structures
Computer science
Computer science
control theory
systems
Electric, optical and optoelectronic circuits
Electronics
Exact sciences and technology
Graph theory
Graphs
Guarantees
Informatics
Information retrieval. Graph
Integer programming
Mathematics
Sciences and techniques of general use
Theoretical computing
Theoretical study. Circuits analysis and design
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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(log2n) 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.
ISSN:0097-5397
1095-7111
DOI:10.1137/s0097539797331671