### Abstract

Original language | English |
---|---|

Pages (from-to) | 80-93 |

Journal | Discrete Applied Mathematics |

Volume | 167 |

DOIs | |

Publication status | Published - 20 Apr 2014 |

### Fingerprint

### Cite this

*Discrete Applied Mathematics*,

*167*, 80-93. https://doi.org/10.1016/j.dam.2013.11.001

}

*Discrete Applied Mathematics*, vol. 167, pp. 80-93. https://doi.org/10.1016/j.dam.2013.11.001

**Book drawings of complete bipartite graphs.** / de Klerk, E.; Pasechnik, D.V.; Salazar, Gelasio.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - Book drawings of complete bipartite graphs

AU - de Klerk, E.

AU - Pasechnik, D.V.

AU - Salazar, Gelasio

PY - 2014/4/20

Y1 - 2014/4/20

N2 - We recall that a book with k pages consists of a straight line (the spine) and k half-planes (the pages), such that the boundary of each page is the spine. If a graph is drawn on a book with k 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 k-page drawing). The page number of a graph G is the minimum k such that G admits a k-page embedding (that is, a k-page drawing with no edge crossings). The k-page crossing number νk(G) of G is the minimum number of crossings in a k-page drawing of G. We investigate the page numbers andk-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 exactk-page crossing number of Kk+1,n for k∈{3,4,5,6}. We also prove the general asymptotic estimate limk→∞limn→∞νk(Kk+1,n)/(2n^2/k^2)=1. Finally, we give general upper bounds for νk(Km,n), and relate these bounds to the k-planar crossing numbers of Km,n and Kn.

AB - We recall that a book with k pages consists of a straight line (the spine) and k half-planes (the pages), such that the boundary of each page is the spine. If a graph is drawn on a book with k 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 k-page drawing). The page number of a graph G is the minimum k such that G admits a k-page embedding (that is, a k-page drawing with no edge crossings). The k-page crossing number νk(G) of G is the minimum number of crossings in a k-page drawing of G. We investigate the page numbers andk-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 exactk-page crossing number of Kk+1,n for k∈{3,4,5,6}. We also prove the general asymptotic estimate limk→∞limn→∞νk(Kk+1,n)/(2n^2/k^2)=1. Finally, we give general upper bounds for νk(Km,n), and relate these bounds to the k-planar crossing numbers of Km,n and Kn.

U2 - 10.1016/j.dam.2013.11.001

DO - 10.1016/j.dam.2013.11.001

M3 - Article

VL - 167

SP - 80

EP - 93

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -