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 [2*n*/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