An Unusual Way to Draw Graphs in Books - SOLVED

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.

UPDATE:

Dujmovic and Wood [DW] have studied this problem and have some
strong results. The call a layout as described in the problem a k-arch-layout, where k is the number of pages. They
showed that if the vertex ordering is fixed, then the graph has a k-arch layout if and only if it
does not contain a set of k+1
edges whose endpoints are in order (1,2),(3,4),...(2k+1,2k+2) . This
gives a characterization in terms of the minimal number of such edge
sequences taken over all permutations of the vertex set.

A graph G is almost k-colorable if there is a set S of k-1 vertices such that G-S is k-colorable. Dujmovic and Wood also
showed:

Theorem: A graph G has arch number at most k if and only if it is almost (k+1)-colorable.

As a corollary, planar graphs have arch number at most 3 and the
bound is tight. Using this result, they show that it is NP-complete to
determine if the arch-number of a graph is at most k.

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.

[DW] V. Dujmovic and D.R. Wood, On linear layout of graphs, preprint.

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

(with thanks to Dujmovic and Wood *vida@cs.mcgill.ca**
davidw@scs.carleton.ca*)

August, 1995