{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T05:10:46Z","timestamp":1737349846316,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_7","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"87-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The Complexity of Planarity Testing"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lov\u00e1sz, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the 20th Annual Symposium on Foundations of Computer Science, pages 218\u2013223. IEEE, 1979.","DOI":"10.1109\/SFCS.1979.34"},{"key":"7_CR2","unstructured":"C. \u00c0lvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Technical Report ECCC-TR96-039, Electronic Colloquium on Computational Complexity, 1996."},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"R. Armoni, A. Ta-Shma, A. Wigderson, and S. Zhou. $$ SL \\subseteq L^{\\tfrac{4} {3}} $$ . In Proceedings of the 29th Annual Symposium on Theory of Computing, pages 230\u2013239. ACM, 1997.","DOI":"10.1145\/258533.258593"},{"key":"7_CR4","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. Journal of Computer and System Sciences, 13:335\u2013379, 1976.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"7_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. Chandra","year":"1984","unstructured":"A. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SIAM Journal on Computing, 13(2):423\u2013439, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S. A. Cook","year":"1987","unstructured":"S. A. Cook and P. McKenzie. Problems complete for L. Journal of Algorithms, 8:385\u2013394, 1987.","journal-title":"Journal of Algorithms"},{"issue":"3","key":"7_CR7","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K. Etessami","year":"1997","unstructured":"K. Etessami. Counting quantifiers, successor relations, and logarithmic space. Journal of Computer and System Sciences, 54(3):400\u2013411, Jun 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR8","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. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2:339\u2013344, 1976.","journal-title":"Theoretical Computer Science"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<99::AID-RSA7>3.0.CO;2-6","volume":"9","author":"A. G\u00e1l","year":"1996","unstructured":"A. G\u00e1l and A. Wigderson. Boolean vs. arithmetic complexity classes: randomized reductions. Random Structures and Algorithms, 9:99\u2013111, 1996.","journal-title":"Random Structures and Algorithms"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"J. Hopcroft and R. Tarjan. Efficient planarity testing. Journal of the ACM, 21:549\u2013568, 1974.","journal-title":"Journal of the ACM"},{"issue":"5","key":"7_CR11","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing, 17(5):935\u2013938, Oct 1988.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR12","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1137\/0211024","volume":"11","author":"J. JaJa","year":"1982","unstructured":"J. Ja\u2019Ja\u2019 and J. Simon. Parallel algorithms in graph theory: Planarity testing. SIAM Journal on Computing, 11:314\u2013328, 1982.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/BF00264160","volume":"17","author":"J. JaJa","year":"1982","unstructured":"J. Ja\u2019Ja\u2019 and J. Simon. Space effcient algorithms for some graph-theoretic problems. Acta Informatica, 17:411\u2013423, 1982.","journal-title":"Acta Informatica"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"M. Karchmer and A. Wigderson. On span programs. In Proceedings of the 8th Conference on Structure in Complexity Theory, pages 102\u2013111. IEEE Computer Society Press, 1993.","DOI":"10.1109\/SCT.1993.336536"},{"key":"7_CR15","first-page":"191","volume":"28","author":"R. M. Karp","year":"1982","unstructured":"R. M. Karp and R. J. Lipton. Turing machines that take advice. L\u2019 Ensignement Math\u00e9matique, 28:191\u2013210, 1982.","journal-title":"L\u2019 Ensignement Math\u00e9matique"},{"key":"7_CR16","unstructured":"A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing in graphs. In Theory of Graphs: International Symposium, pages 215\u2013232, New York, 1967. Gordon and Breach."},{"key":"7_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1007\/3-540-48686-0_13","volume-title":"Proceedings of the Fifth Annual International Computing and Combinatorics Conference COCOON","author":"M. Mahajan","year":"1999","unstructured":"M. Mahajan, P. R. Subramanya, and V. Vinay. A combinatorial algorithm for Pfaffians. In Proceedings of the Fifth Annual International Computing and Combinatorics Conference COCOON, LNCS Volume 1627, pages 134\u2013143. Springer-Verlag, 1999. DIMACS Technical Report 99-39."},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(86)90153-2","volume":"47","author":"Y. Maon","year":"1986","unstructured":"Y. Maon, B. Schieber, and U. Vishkin. Parallel ear decomposition search (EDS) and st-numbering in graphs. Theoretical Computer Science, 47:277\u2013296, 1986.","journal-title":"Theoretical Computer Science"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in O(log1.5 n) space. In Proceedings of the 33rd Annual Smposium on Foundations of Computer Science, pages 24\u201329. IEEE Computer Society Press, 1992.","DOI":"10.1109\/SFCS.1992.267822"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ta-Shma. Symmetric Logspace is closed under complement. Chicago Journal of Theoretical Computer Science, 1995.","DOI":"10.1145\/225058.225101"},{"key":"7_CR21","unstructured":"V. Ramachandran. Parallel open ear decomposition with applications to graph biconnectivity and triconnectivity. In J. Reif, editor, Synthesis of Parallel Algorithms. Morgan Kaumann, 1993."},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1016\/S0022-0000(05)80070-4","volume":"49","author":"V. Ramachandran","year":"1994","unstructured":"V. Ramachandran and J. Reif. Planarity testing in parallel. Journal of Computer and System Sciences, 49:517\u2013561, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"7_CR23","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"J. Reif","year":"1984","unstructured":"J. Reif. Symmetric complementation. Journal of the ACM, 31(2):401\u2013421, 1984.","journal-title":"Journal of the ACM"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"K. Reinhardt and E. Allender. Making nondeterminism unambiguous. In 38 th IEEE Symposium on Foundations of Computer Science (FOCS), pages 244\u2013253, 1997. to appear in SIAM J. Comput.","DOI":"10.1109\/SFCS.1997.646113"},{"key":"7_CR25","doi-asserted-by":"crossref","unstructured":"M. Saks. Randomization and derandomization in space-bounded computation. In Proceedings of the 11th Annual Conference on Computational Complexity, pages 128\u2013149. IEEE Computer Society, 1996.","DOI":"10.1109\/CCC.1996.507676"},{"issue":"2","key":"7_CR26","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177\u2013192, April 1970.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"7_CR27","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"R. Szelepcs\u00e9nyi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26(3):279\u2013284, 1988.","journal-title":"Acta Informatica"},{"key":"7_CR28","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0021-9800(70)80007-2","volume":"8","author":"W. T. Tutte","year":"1970","unstructured":"W. T. Tutte. Toward a theory of crossing numbers. Journal of Combinatorial Theory, 8:45\u201353, 1970.","journal-title":"Journal of Combinatorial Theory"},{"key":"7_CR29","doi-asserted-by":"publisher","first-page":"339","DOI":"10.2307\/1989545","volume":"34","author":"H. Whitney","year":"1932","unstructured":"H. Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society, 34:339\u2013362, 1932.","journal-title":"Transactions of the American Mathematical Society"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T02:56:09Z","timestamp":1737341769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]},"assertion":[{"value":"24 March 2000","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}