{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:01:41Z","timestamp":1725487301590},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404934"},{"type":"electronic","value":"9783540450610"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45061-0_4","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T11:54:04Z","timestamp":1184586844000},"page":"34-46","source":"Crossref","is-referenced-by-count":4,"title":["The SPQR-Tree Data Structure in Graph Drawing"],"prefix":"10.1007","author":[{"given":"Petra","family":"Mutzel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"unstructured":"AGD User Manual (Version 1.1), 1999. Technische Universit\u00e4t Wien, Max-Planck-Institut Saarbr\u00fccken, Universit\u00e4t zu K\u00f6ln, Universit\u00e4t Halle. See also http:\/\/www.ads.tuwien.ac.at\/AGD\/.","key":"4_CR1"},{"unstructured":"D. Alberts, C. Gutwenger, P. Mutzel, and S. N\u00e4her. AGD-library: A library of algorithms for graph drawing. In G. F. Italiano and S. Orlando, editors, Proceedings of the Workshop on Algorithm Engineering (WAE\u2019 97), Sept. 1997.","key":"4_CR2"},{"unstructured":"G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph Drawing. Prentice Hall, 1999.","key":"4_CR3"},{"key":"4_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/BFb0032061","volume-title":"Proc. of the 17th International Colloqium on Automata, Languages and Programming (ICALP)","author":"G. Battista Di","year":"1990","unstructured":"G. Di Battista and R. Tamassia. On-line graph algorithms with SPQR-trees. In M. S. Paterson, editor, Proc. of the 17th International Colloqium on Automata, Languages and Programming (ICALP), volume 443 of Lecture Notes in Computer Science, pages 598\u2013611. Springer-Verlag, 1990."},{"key":"4_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/3-540-37623-2_2","volume-title":"Proc. International Symposium on Graph Drawing","author":"P. Bertolazzi","year":"1998","unstructured":"P. Bertolazzi, G. Di Battista, and W. Didimo. Quasi upward planarity. In S. Whitesides, editor, Proc. International Symposium on Graph Drawing, volume 1547 of LNCS, pages 15\u201329. Springer Verlag, 1998."},{"issue":"8","key":"4_CR6","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1109\/12.868028","volume":"49","author":"P. Bertolazzi","year":"2000","unstructured":"P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers, 49(8):826\u2013840, 2000.","journal-title":"IEEE Transactions on Computers"},{"issue":"1","key":"4_CR7","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1137\/S0097539794279626","volume":"27","author":"P. Bertolazzi","year":"1998","unstructured":"P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Optimal upward planarity testing of single-source digraphs. SIAM J. Comput., 27(1):132\u2013169, 1998.","journal-title":"SIAM J. Comput."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/PL00009182","volume":"19","author":"T. Biedl","year":"1997","unstructured":"T. Biedl, G. Kant, and M. Kaufmann. On triangulating planar graphs under the four-connectivity constraint. Algorithmica, 19:427\u2013446, 1997.","journal-title":"Algorithmica"},{"key":"4_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1002\/net.3230190107","volume":"19","author":"D. Bienstock","year":"1989","unstructured":"D. Bienstock and C. L. Monma. Optimal enclosing regions in planar graphs. Networks, 19:79\u201394, 1989.","journal-title":"Networks"},{"issue":"1","key":"4_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BF01840379","volume":"5","author":"D. Bienstock","year":"1990","unstructured":"D. Bienstock and C. L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica, 5(1):93\u2013109, 1990.","journal-title":"Algorithmica"},{"unstructured":"Z.Z. Chen, X. He, and C.-H. Huang. Finding double euler trails of planar graphs in linear time. In 40th Annual Symposium on Foundations of Computer Science, pages 319\u2013329. IEEE, 1999.","key":"4_CR11"},{"key":"4_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BFb0054325","volume-title":"Proc. 3rd Latin American Symposium on theoretical informatics (LATIN)","author":"E. Dahlhaus","year":"1998","unstructured":"E. Dahlhaus. Linear time algorithm to recognize clustered planar graphs and its parallelization. In Proc. 3rd Latin American Symposium on theoretical informatics (LATIN), volume 1380 of LNCS, pages 239\u2013248. Springer Verlag, 1998."},{"doi-asserted-by":"crossref","unstructured":"G. Di Battista and R. Tamassia. Incremental planarity testing. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 436\u2013441, 1989.","key":"4_CR13","DOI":"10.1109\/SFCS.1989.63515"},{"key":"4_CR14","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/BF01961541","volume":"15","author":"G. Battista Di","year":"1996","unstructured":"G. Di Battista and R. Tamassia. On-line maintanance of triconnected components with SPQR-trees. Algorithmica, 15:302\u2013318, 1996.","journal-title":"Algorithmica"},{"issue":"5","key":"4_CR15","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G. Battista Di","year":"1996","unstructured":"G. Di Battista and R. Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956\u2013997, 1996.","journal-title":"SIAM J. Comput."},{"key":"4_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/3-540-60313-1_145","volume-title":"Algorithms \u2014 ESA\u2019 95, Third Annual European Symposium","author":"Q.-W. Feng","year":"1995","unstructured":"Q.-W. Feng, R.-F. Cohen, and P. Eades. Planarity for clustered graphs. In P. Spirakis, editor, Algorithms \u2014 ESA\u2019 95, Third Annual European Symposium, volume 979 of Lecture Notes in Computer Science, pages 213\u2013226. Springer-Verlag, 1995."},{"unstructured":"E.D. Giacomo, G. Liotta, and S.K. Wismath. Drawing series-parallel graphs on a box. In Proc. 14th Canadian Conference on Computational Geometry, 2002.","key":"4_CR17"},{"key":"4_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/3-540-45875-1_24","volume-title":"Software Visualization","author":"C. Gutwenger","year":"2002","unstructured":"C. Gutwenger, M. J\u00fcnger, G. W. Klau, S. Leipert, and P. Mutzel. Graph drawing algorithm engineering with AGD. In S. Diehl, editor, Software Visualization, volume 2269 of LNCS, pages 307\u2013323. Springer Verlag, 2002."},{"key":"4_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/3-540-36151-0_21","volume-title":"Proc. 10th International Symposium on Graph Drawing","author":"C. Gutwenger","year":"2002","unstructured":"C. Gutwenger, M. J\u00fcnger, S. Leipert, P. Mutzel, and M. Percan. Advances in c-planarity testing of clustered graphs. In M.T. Goodrich and S.G. Kobourov, editors, Proc. 10th International Symposium on Graph Drawing, volume 2528 of LNCS, pages 220\u2013235. Springer Verlag, 2002."},{"unstructured":"C. Gutwenger, K. Klein, J. Kupke, S. Leipert, P. Mutzel, and M. J\u00fcnger. Graph drawing library by OREAS.","key":"4_CR20"},{"doi-asserted-by":"crossref","unstructured":"C. Gutwenger and P. Mutzel. A linear time implementation of SPQR trees. In J. Marks, editor, Graph Drawing (Proc. 2000), volume 1984 of Lecture Notes in. Computer Science, pages 77\u201390. Springer-Verlag, 2001.","key":"4_CR21","DOI":"10.1007\/3-540-44541-2_8"},{"unstructured":"C. Gutwenger and P. Mutzel. Graph embedding with maximum external face and minimum depth. Technical report, Vienna University of Technology, Institute of Computer Graphics and Algorithms, 2003.","key":"4_CR22"},{"unstructured":"C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete A lgorithms (SODA\u2019 2001), pages 246\u2013255, Washington, DC, 2001. ACM Press.","key":"4_CR23"},{"key":"4_CR24","series-title":"Lect Notes Comput Sci","first-page":"220","volume-title":"Proc. 9th International Symposium on Graph Drawing (GD 2001)","author":"S. Hong","year":"2002","unstructured":"S. Hong. Drawing graphs symmetrically in three dimensions. In P. Mutzel, M. J\u00fcnger, and S. Leipert, editors, Proc. 9th International Symposium on Graph Drawing (GD 2001), volume 2265 of LNCS, pages 220\u2013235. Springer Verlag, 2002."},{"issue":"3","key":"4_CR25","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J. E. Hopcroft","year":"1973","unstructured":"J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput., 2(3):135\u2013158, 1973.","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"M. J\u00fcnger and P. Mutzel. Graph Drawing Software. Mathematics and Visualization. Springer-Verlag, 2003. to appear.","key":"4_CR26","DOI":"10.1007\/978-3-642-18638-7"},{"key":"4_CR27","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1215\/S0012-7094-37-00336-3","volume":"3","author":"S. MacLaine","year":"1937","unstructured":"S. MacLaine. A structural characterization of planar combinatorial graphs. Duke Math. J., 3:460\u2013472, 1937.","journal-title":"Duke Math. J."},{"key":"4_CR28","series-title":"Lect Notes Comput Sci","volume-title":"Graph Drawing 2001 (Proc. 9th International Symposium)","year":"2002","unstructured":"P. Mutzel, S. Leipert, and M. J\u00fcnger, editors. Graph Drawing 2001 (Proc. 9th International Symposium), volume 2265 of LNCS. Springer Verlag, 2002."},{"key":"4_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/3-540-48777-8_27","volume-title":"Proceedings of the Seventh Conference on Integer Programming and Combinatorial Optimization (IPCO)","author":"P. Mutzel","year":"1999","unstructured":"P. Mutzel and R. Weiskircher. Optimizing over all combinatorial embeddings of a planar graph. In G. Cornu\u00e9jols, R. Burkard, and G. Woeginger, editors, Proceedings of the Seventh Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 1610 of LNCS, pages 361\u2013376. Springer Verlag, 1999."},{"key":"4_CR30","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/3-540-44968-X_10","volume-title":"Computing and Combinatorics, Proc. Sixth Annual Internat. Conf. (COCOON\u2019 2000)","author":"P. Mutzel","year":"2000","unstructured":"P. Mutzel and R. Weiskircher. Computing optimal embeddings for planar graphs. In D.-Z. Du, P. Eades, V. Estivill-Castro, X. Lin, and A. Sharma, editors, Computing and Combinatorics, Proc. Sixth Annual Internat. Conf. (COCOON\u2019 2000), volume 1858 of LNCS, pages 95\u2013104. Springer Verlag, 2000."},{"key":"4_CR31","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/3-540-45253-2_33","volume-title":"Algorithms \u2014 ESA 2000, Annual European Symposium","author":"M. Pizzonia","year":"2000","unstructured":"M. Pizzonia and R. Tamassia. Minimum depth graph embedding. In M. Paterson, editor, Algorithms \u2014 ESA 2000, Annual European Symposium, volume 1879 of Lecture Notes in Computer Science, pages 356\u2013367. Springer-Verlag, 2000."},{"issue":"2","key":"4_CR32","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1109\/TSMC.1981.4308636","volume":"SMC-11","author":"K. Sugiyama","year":"1981","unstructured":"K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man Cybern., SMC-11(2):109\u2013125, 1981.","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"4_CR33","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizeki, and N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs. J. Assoc. Comput. Mach., 29:623\u2013641, 1982.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"4_CR34","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1137\/0216030","volume":"16","author":"R. Tamassia","year":"1987","unstructured":"R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421\u2013444, 1987.","journal-title":"SIAM J. Comput."},{"key":"4_CR35","series-title":"Technical Report","volume-title":"Finding the triconnected components of a graph","author":"R. Tarjan","year":"1972","unstructured":"R. Tarjan and J. Hopcroft. Finding the triconnected components of a graph. Technical Report 72-140, Dept. of Computer Science, Cornell University, Ithaca, 1972."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45061-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,30]],"date-time":"2019-04-30T23:13:54Z","timestamp":1556666034000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45061-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404934","9783540450610"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-45061-0_4","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}