DIMACS TR: 98-46

On Crossing Sets, Disjoint Sets and the Pagenumber

Authors: Farhad Shahrokhi and Weiping Shi


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