{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:57Z","timestamp":1787337477711,"version":"3.56.0"},"reference-count":13,"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":[[1999,1]]},"abstract":"<jats:p>Stack layouts and queue layouts of undirected graphs have been used to model problems in fault tolerant computing and in parallel process scheduling. However, problems in parallel process scheduling are more accurately modeled by stack and queue layouts of directed acyclic graphs (dags). A stack layout 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 order. A queue layout is defined in an analogous manner. The stacknumber (queuenumber) of a dag is the smallest number of stacks (queues) required for its stack layout (queue layout). This paper presents algorithmic results---in particular, linear time algorithms for recognizing 1-stack dags and 1-queue dags, and proofs of NP-completeness for the problem of recognizing a 4-queue dag and the problem of recognizing a 6-stack dag. The companion paper (Part I [SIAM J. Comput., 28 (1999), pp. 1510--1539.]) presents combinatorial results.<\/jats:p>","DOI":"10.1137\/s0097539795291550","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1588-1626","source":"Crossref","is-referenced-by-count":55,"title":["Stack and Queue Layouts of Directed Acyclic Graphs: Part II"],"prefix":"10.1137","volume":"28","author":[{"given":"Lenwood S.","family":"Heath","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sriram V.","family":"Pemmaraju","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80045-1"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"M. Chandramouli, A. Diwan, Upward numbering testing for triconnected graphs, Lecture Notes in Comput. Sci., Vol. 1027, Springer, Berlin, 1996, 140\u201315197d:68153","DOI":"10.1007\/BFb0021798"},{"key":"R4","unstructured":"M. Chandramouli,\n                      Upward Planar Graph Drawings\n                      , Ph.D. thesis, IIT Bombay, 1994."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1109\/21.23105"},{"key":"R6","doi-asserted-by":"crossref","first-page":"103","DOI":"10.5486\/PMD.1966.13.1-4.15","volume":"13","author":"Harary Frank","year":"1966","journal-title":"Publ. Math. Debrecen"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Lenwood Heath, Sriram Pemmaraju, Recognizing leveled\u2010planar dags in linear time, Lecture Notes in Comput. Sci., Vol. 1027, Springer, Berlin, 1996, 300\u201331197e:05093","DOI":"10.1007\/BFb0021813"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193252380"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280287"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Lenwood Heath, Sriram Pemmaraju, Ann Trenk, Stack and queue layouts of directed acyclic graphs, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., Vol. 9, Amer. Math. Soc., Providence, RI, 1993, 5\u2013111221797","DOI":"10.1090\/dimacs\/009\/02"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0221055"},{"key":"R12","first-page":"261","volume":"2","author":"Sysl\u0142o Maciej","year":"1978","journal-title":"Fund. Inform. (4)"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/0603036"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795291550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:51Z","timestamp":1787335971000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795291550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":13,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["10.1137\/S0097539795291550"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795291550","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}