1992/10/01 by Lenwood S. Heath, Arnold L. Rosenberg · 8 citations
Computer Science · Engineering · Mathematics · #Interconnection Networks and Systems #VLSI and FPGA Design Techniques #Optimization and Packing Problems #Book embedding #Combinatorics #Queue #Computer science #Planar graph #Discrete mathematics #Priority queue #Pathwidth #Indifference graph #Mathematics #Parallel computing #Graph #Line graph #Computer network
paper · doi:10.1137/0221055
openalex publication_date 1992/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/12
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.