Stack and queue layouts of directed acyclic graphs: Part I

Stack layouts and queue layouts of undirected graphs have been used to mode l problems in fault-tolerant computing and in parallel process scheduling. However, problems in parallel process scheduling are more accurately modele d by stack and queue layouts of directed acyclic graphs (dags). A stack lay out of a dag is similar to a stack layout of an undirected graph, with the additional requirement that the nodes of the dag be in some topological ord er. A queue layout is defined in an analogous manner. The stacknumber (queu enumber) of a dag is the smallest number of stacks (queues) required for it s stack layout (queue layout). In this paper, bounds are established on the stacknumber and queuenumber of two classes of dags: tree dags and unicycli c dags. In particular, any tree dag can be laid out in 1 stack and in at mo st 2 queues; and any unicyclic dag can be laid out in at most 2 stacks and in at most 2 queues. Forbidden subgraph characterizations of 1-queue tree d ags and 1-queue cycle dags are also presented. Part II of this paper presen ts algorithmic results-in particular, linear time algorithms for recognizin g 1-stack dags and 1-queue dags and proof of NP-completeness for the proble m of recognizing a 4-queue dag and the problem of recognizing a 9-stack dag .