کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418770 | 681718 | 2014 | 14 صفحه PDF | دانلود رایگان |
We recall that a book with kkpages consists of a straight line (the spine ) and kk half-planes (the pages ), such that the boundary of each page is the spine. If a graph is drawn on a book with kk pages in such a way that the vertices lie on the spine, and each edge is contained in a page, the result is a k-page book drawing (or simply a kk-page drawing). The page number of a graph GG is the minimum kk such that GG admits a kk-page embedding (that is, a kk-page drawing with no edge crossings). The kk-page crossing number νk(G)νk(G) of GG is the minimum number of crossings in a kk-page drawing of GG. We investigate the page numbers andkk-page crossing numbers of complete bipartite graphs. We find the exact page numbers of several complete bipartite graphs, and use these page numbers to find the exactkk-page crossing number of Kk+1,nKk+1,n for k∈{3,4,5,6}k∈{3,4,5,6}. We also prove the general asymptotic estimate limk→∞limn→∞νk(Kk+1,n)/(2n2/k2)=1limk→∞limn→∞νk(Kk+1,n)/(2n2/k2)=1. Finally, we give general upper bounds for νk(Km,n)νk(Km,n), and relate these bounds to the kk-planar crossing numbers of Km,nKm,n and KnKn.
Journal: Discrete Applied Mathematics - Volume 167, 20 April 2014, Pages 80–93