{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:29Z","timestamp":1740109409578,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,4,20]],"date-time":"2017-04-20T00:00:00Z","timestamp":1492646400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,11]]},"DOI":"10.1007\/s00224-017-9768-7","type":"journal-article","created":{"date-parts":[[2017,4,20]],"date-time":"2017-04-20T01:28:37Z","timestamp":1492651717000},"page":"1054-1083","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Dynamic Planar Embeddings of Dynamic Graphs"],"prefix":"10.1007","volume":"61","author":[{"given":"Jacob","family":"Holm","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5853-7909","authenticated-orcid":false,"given":"Eva","family":"Rotenberg","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,4,20]]},"reference":[{"issue":"2","key":"9768_CR1","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/1103963.1103966","volume":"1","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Holm, J., De Lichtenberg, K., Thorup, M.: Maintaining information in fully dynamic trees with top trees. ACM Trans. Algor. 1(2), 243\u2013264 (2005)","journal-title":"ACM Trans. Algor."},{"key":"9768_CR2","doi-asserted-by":"crossref","unstructured":"Di Battista, G., Tamassia, R.: Incremental planarity testing. In: 30th Annual Symposium on Foundations of Computer Science, pp. 436\u2013441. IEEE (1989)","DOI":"10.1109\/SFCS.1989.63515"},{"key":"9768_CR3","doi-asserted-by":"crossref","first-page":"956","DOI":"10.1137\/S0097539794280736","volume":"25","author":"G Di Battista","year":"1996","unstructured":"Di Battista, G., Tamassia, R.: On-line planarity testing. SIAM J. Comput. 25, 956\u2013997 (1996)","journal-title":"SIAM J. Comput."},{"key":"9768_CR4","first-page":"599","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201903","author":"D Eppstein","year":"2003","unstructured":"Eppstein, D.: Dynamic generators of topologically embedded graphs Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201903, pp 599\u2013608. Society for Industrial and Applied Mathematics, Philadelphia (2003)"},{"issue":"1","key":"9768_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1996.0002","volume":"52","author":"D Eppstein","year":"1996","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F., Spencer, T. H.: Separator based sparsification: I. Planarity testing and minimum spanning trees. J. Comput. Syst. Sci. 52(1), 3\u201327 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9768_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0196-6774(92)90004-V","volume":"13","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D., Italiano, G. F, Tamassia, R., Tarjan, R. E, Westbrook, J., Yung, M.: Maintenance of a minimum spanning forest in a dynamic plane graph. J. Algor. 13(1), 33\u201354 (1992)","journal-title":"J. Algor."},{"issue":"4","key":"9768_CR7","doi-asserted-by":"crossref","first-page":"781","DOI":"10.1137\/0214055","volume":"14","author":"GN Frederickson","year":"1985","unstructured":"Frederickson, G. N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM J. Comput. 14(4), 781\u2013798 (1985)","journal-title":"SIAM J. Comput."},{"key":"9768_CR8","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1145\/300515.300517","volume":"46","author":"Z Galil","year":"1999","unstructured":"Galil, Z., Italiano, G. F., Sarnak, N.: Fully dynamic planarity testing with applications. J. ACM 46, 28\u201391 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"9768_CR9","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R. E.: Efficient planarity testing. J. ACM 21(4), 549\u2013568 (1974)","journal-title":"J. ACM"},{"key":"9768_CR10","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/3-540-57273-2_57","volume-title":"European Symposium on Algorithms\u2014ESA \u201993: First Annual European Symposium Bad Honnef, Germany. Proceedings","author":"GF Italiano","year":"1993","unstructured":"Italiano, G. F., La Poutr\u00e9, J. A., Rauch, M. H.: Fully dynamic planarity testing in planar embedded graphs. In: Lengauer, T. (ed.) European Symposium on Algorithms\u2014ESA \u201993: First Annual European Symposium Bad Honnef, Germany. Proceedings, pp 212\u2013223. Springer, Berlin Heidelberg (1993)"},{"key":"9768_CR11","doi-asserted-by":"crossref","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. Math. Oper. Res. 648\u2013657 (1994)","DOI":"10.1145\/195058.195422"},{"key":"9768_CR12","first-page":"146","volume-title":"Multiple-source shortest paths in planar graphs","author":"PN Klein","year":"2005","unstructured":"Klein, P. N.: Multiple-source shortest paths in planar graphs, pp 146\u2013155. Society for Industrial and Applied Mathematics, Philadelphia (2005)"},{"key":"9768_CR13","doi-asserted-by":"crossref","first-page":"706","DOI":"10.1145\/195058.195439","volume-title":"Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201994","author":"JA La Poutr\u00e9","year":"1994","unstructured":"La Poutr\u00e9, J.A.: Alpha-algorithms for incremental planarity testing (preliminary version) Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201994, pp 706\u2013715. ACM, New York (1994)"},{"issue":"4","key":"9768_CR14","doi-asserted-by":"crossref","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M Patra\u015fcu","year":"2006","unstructured":"Patra\u015fcu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006). See also STOC\u201904, SODA\u201904","journal-title":"SIAM J. Comput."},{"key":"9768_CR15","first-page":"263","volume-title":"Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201907","author":"M Patrascu","year":"2007","unstructured":"Patrascu, M, Thorup, M.: Planning for fast connectivity updates Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201907, pp 263\u2013271. IEEE Computer Society, Washington (2007)"},{"issue":"3","key":"9768_CR16","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D. D., Tarjan, R. E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9768_CR17","doi-asserted-by":"crossref","first-page":"743","DOI":"10.1112\/plms\/s3-13.1.743","volume":"s3\u201313","author":"WT Tutte","year":"1963","unstructured":"Tutte, W. T.: How to Draw a Graph. Proce. London Math. Soc. s3\u201313(1), 743\u2013767 (1963)","journal-title":"Proce. London Math. Soc."},{"key":"9768_CR18","unstructured":"Tutte, W. T.: Graph Theory. Encyclopedia of Mathematics and its Applications. Addison-Wesley Pub. Co. Advanced Book Program (1984)"},{"key":"9768_CR19","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/3-540-55719-9_86","volume-title":"Automata, Languages and Programming (ICALP), Volume 623 of Lecture Notes in Computer Science","author":"J Westbrook","year":"1992","unstructured":"Westbrook, J.: Fast incremental planarity testing. In: Kuich, W. (ed.) Automata, Languages and Programming (ICALP), Volume 623 of Lecture Notes in Computer Science, pp 342\u2013353. Springer, Berlin Heidelberg (1992)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9768-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9768-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9768-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,21]],"date-time":"2019-09-21T06:00:40Z","timestamp":1569045640000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9768-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,20]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,11]]}},"alternative-id":["9768"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9768-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,4,20]]}}}