{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:01:57Z","timestamp":1787389317356,"version":"build-2736575974"},"reference-count":94,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>Aqueue layout of a graph consists of a total order of the vertices, and a partition of the edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its queue-number. A three-dimensional (straight-line grid) drawing of a graph represents the vertices by points in $\\mathbb{Z}^3$ and the edges by noncrossing line-segments. This paper contributes three main results:<\/jats:p>\n                  <jats:p>(1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph G is closely related to the queue-number of G. In particular, if G is an n-vertex member of a proper minor-closed family of graphs (such as a planar graph), then G has a $\\mathcal{O}(1) \\times \\mathcal{O}(1) \\times \\mathcal{O}(n)$ drawing if and only if G has a $\\mathcal{O}(1)$ queue-number.<\/jats:p>\n                  <jats:p>(2) It is proved that the queue-number is bounded by the tree-width, thus resolving an open problem due to Ganley and Heath [Discrete Appl. Math., 109 (2001), pp. 215--221] and disproving a conjecture of Pemmaraju [Exploring the Powers of Stacks and Queues via Graph Layouts, Ph. D. thesis, Virginia Polytechnic Institute and State University, Blacksburg, VA, 1992]. This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts.<\/jats:p>\n                  <jats:p>(3) It is proved that graphs of bounded tree-width have three-dimensional drawings with $\\mathcal{O}(n)$ volume. This is the most general family of graphs known to admit three-dimensional drawings with $\\mathcal{O}(n)$ volume.<\/jats:p>\n                  <jats:p>The proofs depend upon our results regarding track layouts and tree-partitions of graphs, which may be of independent interest.<\/jats:p>","DOI":"10.1137\/s0097539702416141","type":"journal-article","created":{"date-parts":[[2005,3,28]],"date-time":"2005-03-28T21:00:23Z","timestamp":1112043623000},"page":"553-579","source":"Crossref","is-referenced-by-count":69,"title":["Layout of Graphs with Bounded Tree-Width"],"prefix":"10.1137","volume":"34","author":[{"given":"Vida","family":"Dujmovic","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759792"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1017\/S001708950000358X"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.37236\/1779"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008647514949"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020303"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02762708"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(79)90021-2"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1996.0024"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0854"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90077-3"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00359-0"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00079"},{"key":"R15","unstructured":"I. Bru\u00df and A. Frick,\n                      Fast interactive 3\u2010D graph visualization\n                      , in Proceedings of the International Symposium on Graph Drawing (GD \u20199), F. J. Brandenburg, ed., Lecture Notes in Comput. Sci. 1027, Springer, New York, 1996, pp. 99\u2013110."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00098-7"},{"key":"R17","unstructured":"Kiran Chilakamarri, Nathaniel Dean, Michael Littman, Three\u2010dimensional Tutte embedding, Proceedings of the Twenty\u2010sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995), Vol. 107, 1995, 129\u2013140MR1369261"},{"key":"R18","unstructured":"M. Chrobak, M. Goodrich, and R. Tamassia,\n                      Convex drawings of graphs in two and three dimensions\n                      , in Proceedings of the 12th Annual ACM Symposium on Computational Geometry, 1996, ACM, New York, pp. 319\u2013328."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0608002"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522826"},{"key":"R21","unstructured":"I. F. Cruz and J. P. Twarog,\n                      3D graph drawing with simulated annealing\n                      , in Proceedings of the International Symposium on Graph Drawing (GD \u201995), F. J. Brandenburg, ed., Lecture Notes in Comput. Sci. 1027, Springer, New York, 1996, pp. 162\u2013165."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122694"},{"key":"R23","unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis,\n                      Graph Drawing: Algorithms for the Visualization of Graphs\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1999."},{"key":"R24","unstructured":"E. Di Giacomo,\n                      Drawing series\u2010parallel graphs on restricted integer 3D grids\n                      , in Proceedings of the 11th International Symposium on Graph Drawing (GD \u201903), G. Liotta, ed., Lecture Notes in Comput. Sci. 2912, Springer, New York, pp. 238\u2013246."},{"key":"R25","unstructured":"E. Di Giacomo, G. Liotta, and H. Meijer,\n                      3D Straight\u2010Line Drawings of k\u2010Trees\n                      , Tech. Report 2003\u2010473, School of Computing, Queen\u2019s University, Kingston, ON, Canada, 2003."},{"key":"R26","unstructured":"E. Di Giacomo, G. Liotta, and S. Wismath,\n                      Drawing series\u2010parallel graphs on a box\n                      , in Proceedings of the 14th Canadian Conference on Computational Geometry (CCCG \u201902), The University of Lethbridge, Lethbridge, AB, Canada, 2002, pp. 149\u2013153."},{"key":"R27","unstructured":"E. Di Giacomo and H. Meijer,\n                      Track drawings of graphs with constant queue number\n                      , in Proceedings of the 11th International Symposium on Graph Drawing (GD \u201903), G. Liotta, ed., Lecture Notes in Comput. Sci. 2912, Springer, New York, pp. 214\u2013225."},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/568522.568523"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.2307\/1969503"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200412"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00337-I"},{"key":"R32","unstructured":"V. Dujmovi\u0107, M. Fellows, M. Hallett, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosemand, M. Suderman, S. Whitesides, and D. R. Wood,\n                      On the parameterized complexity of layered graph drawing\n                      , in Proceedings of the 5th Annual European Symposium on Algorithms (ESA \u201901), F. Meyer auf der Heide, ed., Lecture Notes in Comput. Sci. 2161, Springer, New York, 2001, pp. 488\u2013499."},{"key":"R33","unstructured":"Vida Dujmovi\u0107, Pat Morin, David Wood, Path\u2010width and three\u2010dimensional straight\u2010line grid drawings of graphs, Lecture Notes in Comput. Sci., Vol. 2528, Springer, Berlin, 2002, 42\u201353MR2063410"},{"key":"R34","first-page":"497","volume":"6","author":"Dujmovi\u0107 V.","year":"2004","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"R35","unstructured":"Vida Dujmovi\u0107, David Wood, Tree\u2010partitions of k\u2010trees with applications in graph layout, Lecture Notes in Comput. Sci., Vol. 2880, Springer, Berlin, 2003, 205\u20132172005c:05161"},{"key":"R36","unstructured":"Vida Dujmovi\u0107, David Wood, Tree\u2010partitions of k\u2010trees with applications in graph layout, Lecture Notes in Comput. Sci., Vol. 2880, Springer, Berlin, 2003, 205\u20132172005c:05161"},{"key":"R37","first-page":"339","volume":"6","author":"Dujmovi\u0107 Vida","year":"2004","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"R38","unstructured":"Vida Dujmovi\u0107, David Wood, Three\u2010dimensional grid drawings with sub\u2010quadratic volume, Contemp. Math., Vol. 342, Amer. Math. Soc., Providence, RI, 2004, 55\u2013662005e:05098"},{"key":"R39","unstructured":"Peter Eades, Patrick Garvan, Drawing stressed planar graphs in three dimensions, Lecture Notes in Comput. Sci., Vol. 1027, Springer, Berlin, 1996, 212\u201322397d:68155"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-26.3.198"},{"key":"R41","unstructured":"S. Even, A. Itai, Queues, stacks, and graphs, Academic Press, New York, 1971, 71\u20138654:12380"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00075"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20029"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00178-5"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1137\/0601025"},{"key":"R47","unstructured":"A. Garg, R. Tamassia, and P. Vocca,\n                      Drawing with colors\n                      , in Proceedings of the 4th Annual European Symposium on Algorithms (ESA \u201996), J. Diaz and M. Serna, eds., Lecture Notes in Comput. Sci. 1136, Springer, New York, 1996, pp. 12\u201326."},{"key":"R48","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin","year":"1980"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1007\/BF02764716"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90436-6"},{"key":"R52","first-page":"203","volume":"1","author":"Harary Frank","year":"1972","journal-title":"Utilitas Math."},{"key":"R53","unstructured":"T. Hasunuma,\n                      Laying out iterated line digraphs using queues\n                      , in Proceedings of the 11th International Symposium on Graph Drawing (GD \u201903), G. Liotta, ed., Lecture Notes in Comput. Sci. 2912, Springer, New York, 2004, pp. 202\u2013213."},{"key":"R54","doi-asserted-by":"publisher","DOI":"10.1137\/0405031"},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193252380"},{"key":"R56","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795291550"},{"key":"R57","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280287"},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1137\/0221055"},{"key":"R59","doi-asserted-by":"publisher","DOI":"10.1016\/S0095-8956(03)00037-6"},{"key":"R60","unstructured":"Seok\u2010Hee Hong, Drawing graphs symmetrically in three dimensions, Lecture Notes in Comput. Sci., Vol. 2265, Springer, Berlin, 2002, 189\u2013204MR1962428"},{"key":"R61","unstructured":"Seok\u2010Hee Hong, Peter Eades, An algorithm for finding three dimensional symmetry in series parallel digraphs, Lecture Notes in Comput. Sci., Vol. 1969, Springer, Berlin, 2000, 266\u2013277MR1858369"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-1011-4"},{"key":"R63","unstructured":"Seok\u2010Hee Hong, Peter Eades, Aaron Quigley, Sang\u2010Ho Lee, Drawing algorithms for series\u2010parallel digraphs in two and three dimensions, Lecture Notes in Comput. Sci., Vol. 1547, Springer, Berlin, 1998, 198\u2013209MR1717452"},{"key":"R64","unstructured":"M. Kaufmann and D. Wagner, eds.\n                      Drawing Graphs: Methods and Models\n                      , Lecture Notes in Comput. Sci. 2025, Springer, New York, 2001."},{"key":"R65","first-page":"0","author":"Kosto\u010dka A.","year":"1976","journal-title":"Diskret. Analiz"},{"key":"R66","doi-asserted-by":"publisher","DOI":"10.1137\/0215057"},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-74-04119-2"},{"key":"R68","unstructured":"Burkhard Monien, Friedhelm Ramme, Helmut Salmen, A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs, Lecture Notes in Comput. Sci., Vol. 1027, Springer, Berlin, 1996, 396\u2013408MR1400685"},{"key":"R69","unstructured":"Jaroslav Ne\u0161et\u0159il, Patrice Ossona de Mendez, Colorings and homomorphisms of minor closed classes, Algorithms Combin., Vol. 25, Springer, Berlin, 2003, 651\u20136642004m:05112"},{"key":"R70","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1977"},{"key":"R71","unstructured":"L. T. Ollmann, On the book thicknesses of various graphs, in Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, F. Hoffman, R. B. Levow, and R. S. D. Thomas, eds., Congr. Numer. 8, 1973, p. 459."},{"key":"R72","unstructured":"D. I. Ostry,\n                      Some Three\u2010Dimensional Graph Drawing Algorithms\n                      , Master\u2019s thesis, Department of Computer Science and Software Engineering, The University of Newcastle, Australia, 1996."},{"key":"R73","unstructured":"J\u00e1nos Pach, Torsten Thiele, G\u00e9za T\u00f3th, Three\u2010dimensional grid drawings of graphs, Contemp. Math., Vol. 223, Amer. Math. Soc., Providence, RI, 1999, 251\u201325599g:52031"},{"key":"R74","unstructured":"S. V. Pemmaraju,\n                      Exploring the Powers of Stacks and Queues via Graph Layouts\n                      , Ph.D. thesis, Department of Computer Science, Virginia Polytechnic Institute and State University, Blacksburg, VA, 1992."},{"key":"R75","unstructured":"Z. Peng,\n                      Drawing Graphs of Bounded Treewidth\/Pathwidth\n                      , Master\u2019s thesis, Department of Computer Science, University of Auckland, New Zealand, 2001."},{"key":"R76","unstructured":"T. Poranen,\n                      A New Algorithm for Drawing Series\u2010Parallel Digraphs in 3D\n                      , Tech. Report A\u20102000\u201016, Department of Computer and Information Sciences, University of Tampere, Finland, 2000."},{"key":"R77","unstructured":"B. Reed, Algorithmic aspects of tree width, CMS Books Math.\/Ouvrages Math. SMC, Vol. 11, Springer, New York, 2003, 85\u20131072003m:05199"},{"key":"R78","unstructured":"S. Rengarajan, C. Veni Madhavan, Stack and queue number of 2\u2010trees, Lecture Notes in Comput. Sci., Vol. 959, Springer, Berlin, 1995, 203\u201321297m:05082"},{"key":"R79","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"R80","doi-asserted-by":"publisher","DOI":"10.1137\/0205021"},{"key":"R81","volume-title":"Die Baumweite von Graphen als ein Ma\u00dff\u00fcr die Kompliziertheit algorithmischer Probleme","author":"Scheffler Petra","year":"1989"},{"key":"R82","doi-asserted-by":"publisher","DOI":"10.1007\/BF00353652"},{"key":"R83","unstructured":"D. Seese, Tree\u2010partite graphs and the complexity of algorithms (extended abstract), Lecture Notes in Comput. Sci., Vol. 199, Springer, Berlin, 1985, 412\u2013421MR0821258"},{"key":"R84","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1049"},{"key":"R85","first-page":"1","volume":"3","author":"Steinitz E.","year":"1922","journal-title":"Encyclop\u00e4die Math. Wiss."},{"key":"R86","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321704"},{"key":"R87","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2697"},{"key":"R88","unstructured":"C. Ware and G. Franck,\n                      Viewing a graph in a virtual reality display is three times as good as a 2D diagram\n                      , in Proceedings of the IEEE Symposium on Visual Languages (VL \u201994), A. L. Ambler and T. D. Kimura, eds., IEEE Press, Piscataway, NJ, 1994, pp. 182\u2013183."},{"key":"R89","doi-asserted-by":"publisher","DOI":"10.1145\/234972.234975"},{"key":"R90","unstructured":"C. Ware, D. Hui, and G. Franck,\n                      Visualizing object oriented software in three dimensions\n                      , in Proceedings of the IBM Centre for Advanced Studies Conference (CASCON \u201993), Toronto, 1993, pp. 1\u201311."},{"key":"R91","unstructured":"David Wood, Queue layouts, tree\u2010width, and three\u2010dimensional graph drawing, Lecture Notes in Comput. Sci., Vol. 2556, Springer, Berlin, 2002, 348\u20133592004k:68137"},{"key":"R92","unstructured":"D. R. Wood,\n                      Vertex partitions of chordal graphs\n                      , submitted, 2004;"},{"key":"R92","unstructured":"see arXiv:math.CO\/0408098."},{"key":"R93","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\/S0097539702416141","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:16:49Z","timestamp":1787336209000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702416141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":94,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539702416141"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702416141","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}