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 depict graphs (see [CLR]).

Usually graphs are realized as a subspace of books. It is common to require that the vertices lie on the spine but the edges do not cross the spine. An embedding of this type can be described as follows: give a permutation ordering the vertices along the spine and partition the edges so that no two nonadjacent edges ab,cd in the same part appear in order acbd along the spine (i.e., no two are skew). The parts are the edges on a page. Barrett, Heath, and Pemmaraju [BHP] note the similarity to this restriction with stacks (last-in-first-out storage). That is, an edge is stacked when we first encounter an end walking down the spine and unstacked when we encounter the other end. They use this connection by applying a book embedding to schedule processes on stacks.

Another method of storing edges is queues (first-in-first-out storage). The analogous method for storing edges in queues would require that nonadjacent edges ab,cd do not occur in order acdb along the spine (i.e., are nested). They study a variation on book embeddings in which edges may be disjoint (appear in order abcd) and skew, but not nested. In contrast, the usual embedding of the preceding paragraph allows nested and disjoint but not skew edges.

These three terms, skew, nested, and disjoint, cover the three possibilities for how nonadjacent edges can appear. The literature studies two different combinations of these types. We propose studying the third.

Problem: Find the pagenumber of a graph if each page is allowed to contain nested and skew edges, but not disjoint edges.

There are no known applications of this variation on the theme. To my knowledge no one has worked on this. Nevertheless, I like this problem.

[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.

[BHP] A. Trenk Barrett, L.S. Heath, and S.V. Pemmaraju, Stack and queue layouts of directed acyclic graphs, (manuscript).

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

Send comments to dan.archdeacon@uvm.edu