{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:33:43Z","timestamp":1787340823311,"version":"3.56.0"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1992,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/0221055","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:23Z","timestamp":1109227103000},"page":"927-958","source":"Crossref","is-referenced-by-count":107,"title":["Laying Out Graphs Using Queues"],"prefix":"10.1137","volume":"21","author":[{"given":"Lenwood S.","family":"Heath","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Arnold L.","family":"Rosenberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1964.tb04103.x"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226658"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"J. Buss, P. Shor,  On the pagenumber of planar graphs,  Proceedings of the 16th Annual ACM Symposium on Theory of Computing, Washington, DC,  1984,  98\u2013100","DOI":"10.1145\/800057.808670"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0608002"},{"key":"R6","first-page":"463","volume":"2","author":"Erd\u00f6s P.","year":"1935","journal-title":"Compositio Math."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-417750-5.50011-7"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840445"},{"key":"R9","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1137\/0601025"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"L. S. Heath,  Embedding planar graphs in seven pages,  Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, Singer Island, FL,  1984,  74\u201383","DOI":"10.1109\/SFCS.1984.715903"},{"key":"R12","unstructured":"L. S. Heath, Ph.D. Thesis,  Algorithms for Embedding Graphs in Books, Department of Computer Science, University of North Carolina, Chapel Hill, NC,  1985"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0608018"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"L. S. Heath, S. Israil,  The pagenumber of genus g graphs is  O(g),  Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, NY,  1987,  388\u2013397","DOI":"10.1145\/28395.28437"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146643"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0405031"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0214018"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01786986"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0211025"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120403"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"B. Obreni\u0107,  Embedding de Bruijn and shuffle-exchange graphs in five pages,  Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, Hilton Head, SC,  1991,  137\u2013146","DOI":"10.1145\/113379.113392"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, M. Yannakakis,  Towards an architecture-independent analysis of parallel algorithms,  Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, IL,  1988,  510\u2013513","DOI":"10.1145\/62212.62262"},{"key":"R23","unstructured":"A. Reibman,  DIOGENES layouts using queues,  1984, typescript, Department of Computer Science, Duke University, Durham, NC"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676134"},{"key":"R25","first-page":"261","volume":"2","author":"Syslo Maciej M.","year":"1978","journal-title":"Fund. Inform. (4)"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321704"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90032-9"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0221055","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:50:20Z","timestamp":1787338220000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0221055"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,10]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1992,10]]}},"alternative-id":["10.1137\/0221055"],"URL":"https:\/\/doi.org\/10.1137\/0221055","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,10]]}}}