{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:32Z","timestamp":1759638692492,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540557197"},{"type":"electronic","value":"9783540472780"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55719-9_86","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:34:47Z","timestamp":1330252487000},"page":"342-353","source":"Crossref","is-referenced-by-count":18,"title":["Fast incremental planarity testing"],"prefix":"10.1007","author":[{"given":"Jeffery","family":"Westbrook","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"G. D. Battista and R. Tamassia. Incremental planarity testing. In Proc. 30th IEEE FOCS, pages 436\u2013441, 1989.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"G. D. Battista and R. Tamassia. On-line graph algorithms with SPQR-trees. In Proc. 17th ICALP, 1990.","DOI":"10.1007\/BFb0032061"},{"key":"28_CR3","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci., 13:335\u2013379, 1976.","journal-title":"J. Comput. System Sci."},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"P. F. Deitz and D. D. Sleator. Two algorithms for maintaining order in a list. In Proc. 19th ACM STOC, pages 365\u2013372, 1987.","DOI":"10.1145\/28395.28434"},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. M. auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: upper and lower bounds. In Proceedings 29th IEEE FOCS, pages 524\u2013531, 1988.","DOI":"10.1109\/SFCS.1988.21968"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"M. L. Fredman and M. E. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st ACM STOC, pages 345\u2013354, Seattle, WA, May 1989.","DOI":"10.1145\/73007.73040"},{"key":"28_CR7","unstructured":"H. N. Gabow. Data structures for weighted matching and nearest common ancestors with linking. In Proc. 1st ACM-SIAM SODA, pages 434\u2013443, 1990."},{"key":"28_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci., 30:209\u2013211, 1985.","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR9","volume-title":"Graph Theory","author":"F. Harary","year":"1972","unstructured":"F. Harary. Graph Theory. Addison-Wesley, Reading, MA., 1972."},{"issue":"2","key":"28_CR10","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput, 13(2):338\u2013355, 1984.","journal-title":"SIAM J. Comput"},{"key":"28_CR11","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0202012","volume":"2","author":"J. Hopcroft","year":"1973","unstructured":"J. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. SIAM J. Comput, 2:135\u2013158, 1973.","journal-title":"SIAM J. Comput"},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21:549\u2013568, 1974.","journal-title":"J. ACM"},{"key":"28_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0196-6774(87)90024-1","volume":"8","author":"H. Imai","year":"1987","unstructured":"H. Imai and T. Asano. Dynamic orthogonal segment intersection search. Journal of Algorithms, 8:1\u201318, 1987.","journal-title":"Journal of Algorithms"},{"key":"28_CR14","doi-asserted-by":"crossref","unstructured":"G. F. Italiano and Z. Galil. Fully dynamic algorithms for edge connectivity problems. In 23rd ACM STOC, pages 317\u2013327, 1991.","DOI":"10.1145\/103418.103454"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"J.A. La Poutr\u00e9. Lower bounds for the union-find and split-find problems on pointer machines. In Proc. 22nd ACM Symposium on Theory of Computing, pages 34\u201344, 1990.","DOI":"10.1145\/100216.100221"},{"key":"28_CR16","unstructured":"J. A. La Poutr\u00e9. On-line maintenance of triconnected components. These proceedings."},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"V. Ramachandran and J. H. Reif. An optimal parallel algorithm for graph planarity. In Proc. 30th FOCS, pages 282\u2013287, 1989.","DOI":"10.1109\/SFCS.1989.63491"},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22:215\u2013225, 1975.","journal-title":"J. ACM"}],"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-55719-9_86.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:42:18Z","timestamp":1742593338000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55719-9_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557197","9783540472780"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-55719-9_86","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}