Laying Out Graphs Using Queues
Authors:
- Lenwood S. HeathLHLenwood S. Heath
- Arnold L. RosenbergARArnold L. Rosenberg
- 1 October 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (5) , 927-958
Abstract
The problem of laying out the edges of a graph using queues is studied. 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, a problem of sorting with parallel queues, and a problem of scheduling parallel processors. A number of basic results about queue layouts of graphs are established, and these results are contrasted with their analogues for stack layouts of graphs (the book-embedding problem). The 1-queue graphs (they are almost leveled-planar graphs) are characterized. It is proved that the problem of recognizing 1-queue graphs is NP-complete. Queue layouts for some specific classes of graphs are given. Relationships between the queuenumber of a graph and its bandwidth and separator size are presented. An apparent tradeoff between the queuewidth and the number of queues allowed in layouts of complete binary trees is indicated.Keywords
This publication has 20 references indexed in Scilit:
- Comparing Queues and Stacks As Machines for Laying Out GraphsSIAM Journal on Discrete Mathematics, 1992
- The pagenumber of genus g graphs is O( g )Journal of the ACM, 1992
- Embedding Outerplanar Graphs in Small BooksSIAM Journal on Algebraic Discrete Methods, 1987
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI DesignSIAM Journal on Algebraic Discrete Methods, 1987
- Optimal book embeddings of the FFT, benes, and barrel shifter networksAlgorithmica, 1986
- Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle GraphsSIAM Journal on Computing, 1985
- The Complexity of Coloring Circular Arcs and ChordsSIAM Journal on Algebraic Discrete Methods, 1980
- The book thickness of a graphJournal of Combinatorial Theory, Series B, 1979
- QUEUES, STACKS AND GRAPHS1971
- Optimal Rearrangeable Multistage Connecting NetworksBell System Technical Journal, 1964