THE BOOK CROSSING NUMBER OF A GRAPH

Let G be a graph on n vertices and m edges. The book crossing number o f G is defined as the minimum number of edge crossings when the vertic es of G are placed on the spine of a k-page book and edges are drawn o n pages, such that each edge is contained by one page. Our main result s are two polynomial time algorithms to generate near optimal drawing of G on books. The first algorithm give an C(log(2) n) times optimal s olution, on small number of pages, under some restrictions. This algor ithm also gives rise to the first polynomial time algorithm for approx imating the rectilinear crossing number so that the coordinates of ver tices in the plane are small integers, thus resolving a recent open qu estion concerning the rectilinear crossing number. Moreover, using thi s algorithm we improve the best known upper bounds on the rectilinear crossing number. The second algorithm generates a drawing of G with O( m(2)/k(2)) crossings on k pages. this is within a constant multiplicat ive factor from our general lower bound of Omega(m(3)/n(2)k(2)), provi ded that m = Theta(n(2)). (C) 1996 John Wiley & Sons, Inc.