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(n2m1.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 noncrossing) edges are O( t m ). As an application we embed G in a book of O( t m ) pages, in O(n2m1.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. 2000 Academic Press.
