{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:49Z","timestamp":1725664549254},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_77","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:52:53Z","timestamp":1330278773000},"page":"369-380","source":"Crossref","is-referenced-by-count":11,"title":["A linear algorithm for the maximal planar subgraph problem"],"prefix":"10.1007","author":[{"given":"Hristo N.","family":"Djidjev","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"32_CR1","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, G. Lueker, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithm, J. Comp. Syst. Sci. 13, 1976, pp. 335\u2013379.","journal-title":"J. Comp. Syst. Sci."},{"key":"32_CR2","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/0222068","volume":"22","author":"J. Cai","year":"1993","unstructured":"J. Cai, X. Han, and R.E. Tarjan, An O(m log n)-time algorithm for the maximal planar subgraph, SIAM Journal on Computing, 22 (1993), 1142\u20131162.","journal-title":"SIAM Journal on Computing"},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"G. Di Battista, R. Tamassia, Incremental planarity testing, Proc. IEEE Symp. on Found. of Comp. Sci., (1989), 436\u2013441.","DOI":"10.1109\/SFCS.1989.63515"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"G. Di Battista, R. Tamassia, On-line graph algorithms with SPQR trees, Proc. Intern. Colloquium on Automata, Languages and Programming (1990), 598\u2013611.","DOI":"10.1007\/BFb0032061"},{"key":"32_CR5","first-page":"1183","volume":"37","author":"H. N. Djidjev","year":"1984","unstructured":"H. N. Djidjev, On some properties of nonplanar graphs, Compt. rend. Acad. bulg. Sci., vol. 37 (1984), 9, 1183\u20131185.","journal-title":"Compt. rend. Acad. bulg. Sci."},{"key":"32_CR6","doi-asserted-by":"crossref","unstructured":"H.N. Djidjev, J. Reif, An efficient algorithm for the genus problem with explicit construction of forbidden subgraphs, Proc. Annual ACM Symposium on Theory of Computing (1991), pp.337\u2013347.","DOI":"10.1145\/103418.103456"},{"key":"32_CR7","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0304-3975(76)90086-4","volume":"2","author":"S. Even","year":"1976","unstructured":"S. Even and R.E. Tarjan, Computing an st-numbering, Theoretical Computer Science 2 (1976), 339\u2013344.","journal-title":"Theoretical Computer Science"},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. Gabow","year":"1985","unstructured":"H. Gabow and R.E. Tarjan, A linear-time algorithm for a special case of disjoint set union, J. Compu. Syst. Sci., 30 (1985), 209\u2013220.","journal-title":"J. Compu. Syst. Sci."},{"key":"32_CR9","volume-title":"Algorithms and Intractability: A Guide to the Theory of NP Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Algorithms and Intractability: A Guide to the Theory of NP Completeness. San Francisko, Freeman, 1979."},{"key":"32_CR10","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, 1973, pp. 135\u2013158.","journal-title":"SIAM J. Comput."},{"issue":"4","key":"32_CR11","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:4, 1974, pp. 549\u2013568.","journal-title":"J.ACM"},{"key":"32_CR12","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, in Journal of Algorithms 8, 1987, pp. 1\u201318.","journal-title":"Journal of Algorithms"},{"key":"32_CR13","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1109\/43.21845","volume":"8","author":"R. Jayakumar","year":"1989","unstructured":"R. Jayakumar, K. Thulasiraman, and M.N.S. Swamy, O(n 2) algorithms for graph planarization, IEEE Trans. on Comp.-Aided Design 8 (1989), 257\u2013267.","journal-title":"IEEE Trans. on Comp.-Aided Design"},{"key":"32_CR14","doi-asserted-by":"crossref","unstructured":"J.A. La Poutr\u00e9, Alpha-algorithms for incremental planarity testing, Proc. of the Ann. ACM Symp. on Theory of Comput., 1994, 706\u2013715.","DOI":"10.1145\/195058.195439"},{"key":"32_CR15","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 (1975), 215\u2013225.","journal-title":"J. ACM"},{"key":"32_CR16","doi-asserted-by":"crossref","unstructured":"J. Westbrook, Fast incremental planarity testing, Proc. Int. Col. on Automata, Languages, and Programming, 1992, 342\u2013353.","DOI":"10.1007\/3-540-55719-9_86"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_77.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:56:13Z","timestamp":1605646573000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_77"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_77","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}