Premium
The book crossing number of a graph
Author(s) -
Shahrokhi Farhad,
Székely László A.,
Sýkora Ondrej,
Vrt'o Imrich
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199604)21:4<413::aid-jgt7>3.0.co;2-s
Subject(s) - combinatorics , crossing number (knot theory) , mathematics , multiplicative function , time complexity , graph , upper and lower bounds , plane (geometry) , discrete mathematics , geometry , intersection (aeronautics) , mathematical analysis , engineering , aerospace engineering
Let G be a graph on n vertices and m edges. The book crossing number of G is defined as the minimum number of edge crossings when the vertices of G are placed on the spine of a k ‐page book and edges are drawn on pages, such that each edge is contained by one page. Our main results are two polynomial time algorithms to generate near optimal drawing of G on books. The first algorithm give an O (log 2 n ) times optimal solution, on small number of pages, under some restrictions. This algorithm also gives rise to the first polynomial time algorithm for approximating the rectilinear crossing number so that the coordinates of vertices in the plane are small integers, thus resolving a recent open question concerning the rectilinear crossing number. Moreover, using this 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 multiplicative factor from our general lower bound of Ω( m 3 / n 2 k 2 ), provided that m = Ψ( n 2 ). © 1996 John Wiley & Sons, Inc.