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

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

author list (cited authors)

  • Shahrokhi, F., & Shi, W.

citation count

  • 19

publication date

  • January 2000