The Pagenumber of Complete Bipartite Graphs 



A page is a closed half-plane. A book is a collection of pages identified along the boundary of the half-planes. This common boundary is called the spine. Books provide another topological space in which to embed graphs. Every graph embeds in a book with three pages, so it is common to put some restrictions on how the graph is drawn. Specifically, we require that all vertices lie on the spine and no edge contains a point on the spine other than its ends.

The pagenumber of a graph G, pn(G), is the fewest number of pages in a book containing G. The pagenumber of the complete graph K_n is {n / 2}, where {x} means round x up to the next integer. Surprisingly, the pagenumber of the complete bipartite graph K_{n,m} is much harder.

Problem: Find the pagenumber of K_{n,m}.

Until recently the best known drawing used {(2n+m)/4} pages (or only n pages if that is fewer). Surprisingly this used ``runs'' of uneven length between the two partite sets. In [MWW] they show that this cannot be beat when m=n by using runs of equal length. They also give the construction achieving this upper bound. They conjectured that this was in face the pagenumber

Recently Hikoe Enomoto found some drawings which use few pages than the conjectured bound. In particular, he draws K_{n,n} in only [2n/3] +1 pages, where [x] denotes the integer part of x. He also draws K_{[n^2/4],n} in n-1 pages. Finally, he gives the asymptotic result min { m : pn (K_{m,n}) = n } = (n^2/4)(1 + o(1)).

The problem was introduced by Kainen [K] and [BK]. Chung, Leighton and Rosenberg [CLR] give some applications to VLSI design. The applications are very interesting and I recommend [CLR] to the interested reader.

Leighton has asked for the page number of the Cartesian product K_n x K_m. I do not know why he was interested in these graphs or if any work has been done on the problem.

References:

[CLR] F. Chung, F. Leighton, and A. Rosenberg, Embedding graphs in books: a layout problem with applications to VLSI design, SIAM Journal on Algebraic and Discrete Methods, 8 (1987) 33-58.

[E] Hikoe Enomoto, On the pagenumber of complete bipartite graphs, manuscript.

[K] P.C. Kainen, An introduction to topological graph theory, in Graphs and Combinatorics, R. Bari and F. Harary, Eds., Springer, New York, 1974, pp. 76-108.

[BK] F. Bernhart and P. C. Kainen, The book thickness of a graph, J. of Combin. Th. B 27 (1979) 320-331.

[MWW] D.J. Muder, M.L. Weaver, and D.B. West, Pagenumber of complete bipartite graphs, J. Graph Theory 12 (1988) 469-489.


Submitted by: Dan Archdeacon, Department of Mathematics and Statistics, University of Vermont, Burlington VT 05405 USA.

Send comments to dan.archdeacon@uvm.edu

August, 1995, last modified September, 2000