On Crossing Sets, Disjoint Sets, and Pagenumber Academic Article uri icon


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

published proceedings

  • Journal of Algorithms

altmetric score

  • 3

author list (cited authors)

  • Shahrokhi, F., & Shi, W.

citation count

  • 21

complete list of authors

  • Shahrokhi, Farhad||Shi, Weiping

publication date

  • January 2000