{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:16Z","timestamp":1725663376739},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540507284"},{"type":"electronic","value":"9783540460763"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1989]]},"DOI":"10.1007\/3-540-50728-0_56","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T20:32:47Z","timestamp":1330201967000},"page":"352-377","source":"Crossref","is-referenced-by-count":2,"title":["O(n2) algorithms for graph planarization"],"prefix":"10.1007","author":[{"given":"R.","family":"Jayakumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Thulasiraman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. N. S.","family":"Swamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"25_CR1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979."},{"issue":"2","key":"25_CR2","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1109\/TCT.1966.1082574","volume":"CT-13","author":"G.J. Fisher","year":"1966","unstructured":"G.J. Fisher and O. Wing, \"Computer Recognition and Extraction of Planar Graphs from the Incidence Matrix\", IEEE Trans. on Circuit Theory, Vol. CT-13, No. 2, 154\u2013163 (June 1966).","journal-title":"IEEE Trans. on Circuit Theory"},{"unstructured":"K. Pasedach, \"Criterion and Algorithms for Determination of Bipartite Subgraphs and their Application to Planarization of Graphs\", in Graphen-Sprachen und Algorithmen auf Graphen, Carl Hanser Verlag, 1976, pp. 175\u2013183.","key":"25_CR3"},{"unstructured":"M. Marek-Sadowska, \"Planarization Algorithm for Integrated Circuits Engineering\", Proc. 1978 IEEE International Symposium on Circuits and Systems, pp. 919\u2013923.","key":"25_CR4"},{"unstructured":"T. Chiba, I. Nishioka, and I. Shirakawa, \"An Algorithm of Maximal Planarization of Graphs\", Proc. 1979 IEEE International Symposium on Circuits and Systems, pp. 649\u2013652.","key":"25_CR5"},{"issue":"4","key":"25_CR6","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"J. Hopcroft and R. Tarjan, \"Efficient Planarity Testing\", J. Assoc. Comput. Mach., Vol. 21, No. 4, 549\u2013568 (October 1974).","journal-title":"J. Assoc. Comput. Mach."},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/3-540-10704-5_9","volume":"108","author":"T. Ozawa","year":"1981","unstructured":"T. Ozawa and H. Takahashi, \"A Graph-Planarization Algorithm and its Application to Random Graphs\", in Graph Theory and Algorithms, Springer-Verlag Lecture Notes in Computer Science, Vol. 108, 1981, pp. 95\u2013107.","journal-title":"Graph Theory and Algorithms"},{"issue":"3","key":"25_CR8","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Lueker, \"Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-tree Algorithms\", Journal of Comp. and Syst. Sciences, Vol. 13, No. 3, 335\u2013379 (December 1976).","journal-title":"Journal of Comp. and Syst. Sciences"},{"key":"25_CR9","first-page":"215","volume-title":"Theory of Graphs: International Symposium: Rome, July 1966","author":"A. Lempel","year":"1967","unstructured":"A. Lempel, S. Even, and I. Cederbaum, \"An Algorithm for Planarity Testing of Graphs\", Theory of Graphs: International Symposium: Rome, July 1966, P. Rosenstiehl (Ed.), Gordon and Breach, New York, 1967, pp. 215\u2013232."},{"key":"25_CR10","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"S. Even, Graph Algorithms, Computer Science Press, Potomac, Maryland, 1979."},{"issue":"8","key":"25_CR11","first-page":"843","volume":"CAS-33","author":"R. Jayakumar","year":"1986","unstructured":"R. Jayakumar, K. Thulasiraman, and M.N.S. Swamy, \"On Maximal Planarization of Non-planar Graphs\", IEEE Trans. on Circuits and Systems, Vol. CAS-33, No. 8, August 1986, pp. 843\u2013844.","journal-title":"IEEE Trans. on Circuits and Systems"},{"key":"25_CR12","volume-title":"Design and Analysis of Graph Algorithms: Spanning Tree Enumeration, Planar Embedding, and Maximal Planarization","author":"R. Jayakumar","year":"1984","unstructured":"R. Jayakumar, \"Design and Analysis of Graph Algorithms: Spanning Tree Enumeration, Planar Embedding, and Maximal Planarization\", Ph.D. Thesis, Electrical Engineering Department, Concordia University, Montreal, Canada, August 1984."},{"issue":"3","key":"25_CR13","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1109\/31.1746","volume":"CAS-35","author":"R. Jayakumar","year":"1988","unstructured":"R. Jayakumar, K. Thulasiraman, and M.N.S. Swamy, \"Planar Embedding: Linear-Time Algorithms for Vertex Placements and Edge Ordering\", IEEE Trans. on Circuits and Systems, Vol. CAS-35, No. 3, March 1988, pp. 334\u2013344.","journal-title":"IEEE Trans. on Circuits and Systems"},{"key":"25_CR14","doi-asserted-by":"crossref","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\", Theo. Comp. Sci., Vol. 2, 339\u2013344 (1976).","journal-title":"Theo. Comp. Sci."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-50728-0_56.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:57:12Z","timestamp":1619571432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-50728-0_56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"ISBN":["9783540507284","9783540460763"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-50728-0_56","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1989]]}}}