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.

The Dujnovic and Wood article has a large bibliography with results on stack, queue, and arch layouts.

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