DIMACS TR: 98-46
On Crossing Sets, Disjoint Sets
and the Pagenumber
Authors: Farhad Shahrokhi and Weiping Shi
ABSTRACT
Let $G=(V,E)$ be a $t$-partite graph
with $n$ vertices and $m$ edges, where the partite sets are given.
We present an $O(n^2m^{1.5})$ time algorithm
to construct drawings
of $G$ in the plane so that the size of the largest
set of pairwise crossing edges, and at the same time,
the size of the largest set of disjoint
(pairwise non-crossing) edges are $O(\sqrt{t\cdot m})$.
As an application we embed $G$ in a book of
$O(\sqrt{t\cdot m})$ pages, in $O(n^2m^{1.5})$ time,
resolving an open question for the pagenumber problem.
A similar result is obtained for the dual of the pagenumber
or the queuenumber.
Our algorithms are obtained by derandomizing a probabilistic proof.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-46.ps.gz
DIMACS Home Page