Book drawings of complete bipartite graphs

E. de Klerk, D.V. Pasechnik, Gelasio Salazar

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)80-93
JournalDiscrete Applied Mathematics
Volume167
DOIs
Publication statusPublished - 20 Apr 2014

Fingerprint

Complete Bipartite Graph
Crossing number
Spine
Asymptotic Estimates
Graph in graph theory
Half-plane
Straight Line
Drawing
Upper bound

Cite this

de Klerk, E. ; Pasechnik, D.V. ; Salazar, Gelasio. / Book drawings of complete bipartite graphs. In: Discrete Applied Mathematics. 2014 ; Vol. 167. pp. 80-93.
@article{acbe02f2b36b4586937d09cd48227e43,
title = "Book drawings of complete bipartite graphs",
abstract = "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.",
author = "{de Klerk}, E. and D.V. Pasechnik and Gelasio Salazar",
year = "2014",
month = "4",
day = "20",
doi = "10.1016/j.dam.2013.11.001",
language = "English",
volume = "167",
pages = "80--93",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

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

In: Discrete Applied Mathematics, Vol. 167, 20.04.2014, p. 80-93.

Research output: Contribution to journalArticleScientificpeer-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 -