Graph Layout Using Queues

Abstract

We study the problem of laying out the edges of a graph using queues. In a k queue layout, vertices of the graph are placed in some linear order and each edge is assigned to exactly one of the k queues so that the edges assigned to each queue obey a first-in/first-out discipline. This layout problem abstracts a design problem of fault-tolerant processor arrays and a problem of sorting with parallel queues. We relate the queue layout problem to the corresponding stack layout problem using stacks (the book embedding problem) and immediately derive some asymptomic bounds for d-valent graph. We show that every 1-queue graph is a 2-stack graph and that every 1-stack graph is a 2-queue graph. We characterize the 1-queue graphs (they are almost leveled-planar graphs) and prove that the problem of recognizing 1-queue graphs is NP-complete. We give some queue layouts for specific classes of graphs. Relationships to cutwidth, bandwidth, and bifurcators are presented. We show a tradeoff between queuenumber and stacknumber for a fixed linear order of the vertices of G.