{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T14:10:27Z","timestamp":1737555027603,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540001584"},{"type":"electronic","value":"9783540361510"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36151-0_5","type":"book-chapter","created":{"date-parts":[[2007,11,16]],"date-time":"2007-11-16T17:14:14Z","timestamp":1195233254000},"page":"42-53","source":"Crossref","is-referenced-by-count":8,"title":["Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs"],"prefix":"10.1007","author":[{"given":"Vida","family":"Dujmovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pat","family":"Morin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David R.","family":"Wood","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,11,8]]},"reference":[{"issue":"6","key":"5_CR1","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender, A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305\u20131317, 1996.","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"5_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H. L. Bodlaender","year":"1998","unstructured":"H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1\u20132):1\u201345, 1998.","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR3","unstructured":"F. J. Brandenburg, ed., Proc. International Symp. on Graph Drawing (GD\u2019 95), vol. 1027 of Lecture Notes in Comput. Sci., Springer, 1996."},{"key":"5_CR4","doi-asserted-by":"crossref","unstructured":"I. Bru\u00df and A. Frick, Fast interactive 3-D graph visualization. In [3], pp. 99\u2013110.","DOI":"10.1007\/BFb0021794"},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0020-0190(97)00098-7","volume":"63","author":"T. Calamoneri","year":"1997","unstructured":"T. Calamoneri and A. Sterbini, 3D straight-line grid drawing of 4-colorable graphs. Inform. Process. Lett., 63(2):97\u2013102, 1997.","journal-title":"Inform. Process. Lett."},{"key":"5_CR6","unstructured":"K. Chilakamarri, N. Dean, and M. Littman, Three-dimensional Tutte embedding. In Proc. 26th Southeastern International Conf. on Combinatorics, Graph Theory and Computing, vol. 107 of Cong. Numer., pp. 129\u2013140, 1995."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"M. Chrobak, M. Goodrich, and R. Tamassia, Convex drawings of graphs in two and three dimensions. In Proc. 12th Annual ACM Symp. on Comput. Geom., pp. 319\u2013328, 1996.","DOI":"10.1145\/237218.237401"},{"issue":"2","key":"5_CR8","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF02522826","volume":"17","author":"R. F. Cohen","year":"1996","unstructured":"R. F. Cohen, P. Eades, T. Lin, and F. Ruskey, Three-dimensional graph drawing. Algorithmica, 17(2):199\u2013208, 1996","journal-title":"Algorithmica"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"I. F. Cruz and J. P. Twarog, 3D graph drawing with simulated annealing. In [3], pp. 162\u2013165.","DOI":"10.1007\/BFb0021800"},{"issue":"1","key":"5_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/BF02122694","volume":"10","author":"H. Fraysseix de","year":"1990","unstructured":"H. de Fraysseix, J. Pach, and R. Pollack, How to draw a planar graph on a grid. Combinatorica, 10(1):41\u201351, 1990.","journal-title":"Combinatorica"},{"key":"5_CR11","unstructured":"E. di Giacomo, G. Liotta, and S. Wismath, Drawing series-parallel graphs on a box. In S. Wismath, ed., Proc. 14th Canadian Conf. on Computational Geometry (CCCG\u2019 02), The University of Lethbridge, Canada, 2002."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows, Parameterized complexity. Springer, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"5_CR13","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, On the parameterized complexity of layered graph drawing. In F. Meyer auf der Heide, ed., Proc. 5th Annual European Symp. on Algorithms (ESA\u2019 01), vol. 2161 of Lecture Notes in Comput. Sci., pp. 488\u2013499, Springer, 2001."},{"key":"5_CR14","series-title":"Tech. Rep.","volume-title":"Tree-partitions of k-trees with applications in graph layout","author":"V. Dujmovi\u0107","year":"2002","unstructured":"V. Dujmovi\u0107 and D. R. Wood, Tree-partitions of k-trees with applications in graph layout. Tech. Rep. TR-02-03, School of Computer Science, Carleton University, Ottawa, Canada, 2002."},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"P. Eades and P. Garvan, Drawing stressed planar graphs in three dimensions. In [3], pp. 212\u2013223.","DOI":"10.1007\/BFb0021805"},{"key":"5_CR16","first-page":"198","volume":"26","author":"P. Erd\u00f6s","year":"1951","unstructured":"P. Erd\u00f6s, Appendix. In K. F. Roth, On a problem of Heilbronn. J. London Math. Soc., 26:198\u2013204, 1951.","journal-title":"J. London Math. Soc."},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"S. Felsner, S. Wismath, and G. Liotta, Straight-line drawings on restricted integer grids in two and three dimensions. In [28], pp. 328\u2013342.","DOI":"10.1007\/3-540-45848-4_26"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"A. Garg, R. Tamassia, and P. Vocca, Drawing with colors. In J. Diaz and M. Serna, eds., Proc. 4th Annual European Symp. on Algorithms (ESA\u2019 96), vol. 1136 of Lecture Notes in Comput. Sci., pp. 12\u201326, Springer","DOI":"10.1007\/3-540-61680-2_43"},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"A. Gupta and N. Nishimura, Sequential and parallel algorithms for embedding problems on classes of partial k-trees. In Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT\u2019 94), vol. 824 of Lecture Notes in Comput. Sci., pp. 172\u2013182, Springer, 1984.","DOI":"10.1007\/3-540-58218-5_16"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"A. Gupta, N. Nishimura, A. Proskurowski, and P. Ragde, Embeddings of k-connected graphs of pathwidth k. In M. M. Halldorsson, ed., Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT\u2019 00), vol. 1851 of Lecture Notes in Comput. Sci., pp. 111\u2013124, Springer, 2000.","DOI":"10.1007\/3-540-44985-X_11"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"P. Hlin\u011bn\u00fd, Crossing-critical graphs and path-width. In [28], pp. 102\u2013114.","DOI":"10.1007\/3-540-45848-4_9"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"S.-H. Hong, Drawing graphs symmetrically in three dimensions. In [28], pp. 189\u2013204.","DOI":"10.1007\/3-540-45848-4_16"},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"S.-H. Hong and P. Eades, An algorithm for finding three dimensional symmetry in series parallel digraphs. In D. Lee and S.-H. Teng, eds., Proc. 11th International Conf. on Algorithms and Computation (ISAAC\u2019 00), vol. 1969 of Lecture Notes in Comput. Sci., pp. 266\u2013277, Springer, 2000.","DOI":"10.1007\/3-540-40996-3_23"},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"S.-H. Hong and P. Eades, An algorithm for finding three dimensional symmetry in trees. In J. Marks, ed., Proc. 8th International Symp. on Graph Drawing (GD\u2019 00), vol. 1984 of Lecture Notes in Comput. Sci., pp. 360\u2013371, Springer, 2001.","DOI":"10.1007\/3-540-44541-2_34"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"S.-H. Hong, P. Eades, A. Quigley, and S.-H. Lee, Drawing algorithms for series-parallel digraphs in two and three dimensions. In S. Whitesides, ed., Proc. 6th International Symp. on Graph Drawing (GD\u2019 98), vol. 1547 of Lecture Notes in Comput. Sci., pp. 198\u2013209, Springer, 1998.","DOI":"10.1007\/3-540-37623-2_15"},{"issue":"3","key":"5_CR26","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1137\/0215057","volume":"15","author":"F. T. Leighton","year":"1986","unstructured":"F. T. Leighton and A. L. Rosenberg, Three-dimensional circuit layouts. SIAM J. Comput., 15(3):793\u2013813, 1986.","journal-title":"SIAM J. Comput."},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"B. Monien, F. Ramme, and H. Salmen, A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs. In [3], pp. 396\u2013408.","DOI":"10.1007\/BFb0021823"},{"key":"5_CR28","unstructured":"P. Mutzel, M. J\u00fcnger, and S. Leipert, eds., Proc. 9th International Symp. on Graph Drawing (GD\u2019 01), vol. 2265 of Lecture Notes in Comput. Sci., Springer, 2002."},{"key":"5_CR29","volume-title":"Some Three-Dimensional Graph Drawing Algorithms","author":"D. I. Ostry","year":"1996","unstructured":"D. I. Ostry, Some Three-Dimensional Graph Drawing Algorithms. Master\u2019s thesis, Department of Computer Science and Software Engineering, The University of Newcastle, Australia, 1996."},{"key":"5_CR30","unstructured":"J. Pach, T. Thiele, and G. T\u00f3th, Three-dimensional grid drawings of graphs. In G. Di Battista, ed., Proc. 5th International Symp. on Graph Drawing (GD\u2019 97), vol. 1353 of Lecture Notes in Comput. Sci., pp. 47\u201351, Springer, 1998."},{"key":"5_CR31","volume-title":"Drawing Graphs of Bounded Treewidth\/Pathwidth","author":"Z. Peng","year":"2001","unstructured":"Z. Peng, Drawing Graphs of Bounded Treewidth\/Pathwidth. Master\u2019s thesis, Department of Computer Science, University of Auckland, New Zealand, 2001."},{"key":"5_CR32","series-title":"Tech. Rep.","volume-title":"A new algorithm for drawing series-parallel digraphs in 3D","author":"T. Poranen","year":"2000","unstructured":"T. Poranen, A new algorithm for drawing series-parallel digraphs in 3D. Tech. Rep. A-2000-16, Dept. of Computer and Information Sciences, University of Tampere, Finland, 2000."},{"issue":"4","key":"5_CR33","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/BF00353652","volume":"5","author":"W. Schnyder","year":"1989","unstructured":"W. Schnyder, Planar graphs and poset dimension. Order, 5(4):323\u2013343, 1989.","journal-title":"Order"},{"issue":"2","key":"5_CR34","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M. Thorup","year":"1998","unstructured":"M. Thorup, All structured programs have small tree-width and good register allocation. Information and Computation, 142(2):159\u2013181, 1998.","journal-title":"Information and Computation"},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"C. Ware and G. Franck, Viewing a graph in a virtual reality display is three times as good as a 2D diagram. In A. L. Ambler and T. D. Kimura, eds., Proc. IEEE Symp. Visual Languages (VL\u2019 94), pp. 182\u2013183, IEEE, 1994.","DOI":"10.1109\/VL.1994.363621"},{"key":"5_CR36","unstructured":"C. Ware, D. Hui, and G. Franck, Visualizing object oriented software in three dimensions. In Proc. IBM Centre for Advanced Studies Conf. (CASCON\u2019 93), pp. 1\u201311, 1993."},{"key":"5_CR37","doi-asserted-by":"crossref","unstructured":"R. Weiskircher, Drawing planar graphs. In M. Kaufmann and D. Wagner, eds., Drawing Graphs: Methods and Models, vol. 2025 of Lecture Notes in Comput. Sci., pp. 23\u201345, Springer, 2001.","DOI":"10.1007\/3-540-44969-8_2"},{"key":"5_CR38","series-title":"Tech. Rep.","volume-title":"Queue layouts, tree-width, and three-dimensional graph drawing","author":"D. R. Wood","year":"2002","unstructured":"D. R. Wood, Queue layouts, tree-width, and three-dimensional graph drawing. Tech. Rep. TR-02-02 (revised), School of Computer Science, Carleton University, Ottawa, Canada, August, 2002."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36151-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T13:37:07Z","timestamp":1737553027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36151-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540001584","9783540361510"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/3-540-36151-0_5","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}