{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T16:51:02Z","timestamp":1771606262796,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540415541","type":"print"},{"value":"9783540445418","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44541-2_8","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T16:01:32Z","timestamp":1184601692000},"page":"77-90","source":"Crossref","is-referenced-by-count":112,"title":["A Linear Time Implementation of SPQR-Trees"],"prefix":"10.1007","author":[{"given":"Carsten","family":"Gutwenger","sequence":"first","affiliation":[]},{"given":"Petra","family":"Mutzel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,5,27]]},"reference":[{"key":"8_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1007\/BFb0032061","volume-title":"On-line graph algorithms with SPQR-trees","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 Prog ramming (ICALP), volume 443 of Lecture Notes in Computer Science, pages 598\u2013611. Springer-Verlag, 1990."},{"key":"8_CR2","series-title":"Lect Notes Comput Sci","first-page":"331","volume-title":"Computing orthogonal drawings with the minimum number of bends","author":"P. Bertolazzi","year":"1998","unstructured":"P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. In Proc. 5th Workshop Algorithms, Data Struct., volume 1272 of Lecture Notes in Computer Science, pages 331\u2013344, 1998."},{"issue":"1","key":"8_CR3","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."},{"issue":"1","key":"8_CR4","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"},{"key":"8_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BFb0054325","volume-title":"A linear time algorithm to recognize clustered planar graphs and its parallelization","author":"E. Dahlhaus","year":"1998","unstructured":"Elias Dahlhaus. A linear time algorithm to recognize clustered planar graphs and its parallelization. In C. L. Lucchesi and A. V. Moura, editors, LATIN\u2019 98: Theoretical Informatics, Third Latin American Symposium, volume 1380 of Lecture Notes in Computer Science, pages 239\u2013248. Springer-Verlag, 1998."},{"key":"8_CR6","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0925-7721(96)00005-3","volume":"7","author":"G. Battista Di","year":"1997","unstructured":"G. Di Battista, A. Garg, G. Liotta, R. Tamassia, and F. Vargiu. An experimental comparision of four graph drawing algorithms. Comput. Geom. Theory Appl., 7:303\u2013326, 1997.","journal-title":"Comput. Geom. Theory Appl."},{"key":"8_CR7","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.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"8_CR8","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":"8_CR9","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":"8_CR10","unstructured":"W. Didimo. Dipartimento di Informatica e Automazione, Universit\u00e0 di Roma Tre, Rome, Italy, Personal Communication."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"C. Gutwenger and P. Mutzel. A linear time implementation of SPQR-trees. Technical report, Technische Universit\u00e4t Wien, 2000. To appear.","DOI":"10.1007\/3-540-44541-2_8"},{"key":"8_CR12","unstructured":"C. Gutwenger, P. Mutzel, and R. Weiskircher. Inserting an edge into a planar graph. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u2019 01). ACM Press, 2001. To appear."},{"issue":"3","key":"8_CR13","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."},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. E. Hopcroft","year":"1974","unstructured":"J. E. Hopcroft and R. E. Tarjan. Efficient planarity testing. Journal of the ACM, 21:549\u2013568, 1974.","journal-title":"Journal of the ACM"},{"issue":"1","key":"8_CR15","first-page":"4","volume":"16","author":"G. Kant","year":"1996","unstructured":"G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, Special Issue on Graph Drawing, 16(1):4\u201332, 1996.","journal-title":"Algorithmica, Special Issue on Graph Drawing"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1145\/65950.65952","volume":"36","author":"T. Lengauer","year":"1989","unstructured":"T. Lengauer. Hierarchical planarity testing. Journal of the ACM, 36:474\u2013509, 1989.","journal-title":"Journal of the ACM"},{"key":"8_CR17","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":"8_CR18","unstructured":"K. Mehlhorn and S. N\u00e4her. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999. to appear."},{"key":"8_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/3-540-48777-8_27","volume-title":"Optimizing over all combinatorial embeddings of a planar graph","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."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44541-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T03:19:48Z","timestamp":1556680788000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44541-2_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540415541","9783540445418"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44541-2_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}