{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,11]],"date-time":"2026-02-11T14:08:03Z","timestamp":1770818883456,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,2,5]],"date-time":"2009-02-05T00:00:00Z","timestamp":1233792000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,11]]},"DOI":"10.1007\/s00224-009-9172-z","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T19:31:24Z","timestamp":1233775884000},"page":"675-723","source":"Crossref","is-referenced-by-count":30,"title":["Planar and Grid Graph Reachability Problems"],"prefix":"10.1007","volume":"45","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"David A.","family":"Mix Barrington","sequence":"additional","affiliation":[]},{"given":"Tanmoy","family":"Chakraborty","sequence":"additional","affiliation":[]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[]},{"given":"Sambuddha","family":"Roy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,2,5]]},"reference":[{"key":"9172_CR1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/j.ic.2003.09.002","volume":"189","author":"E. Allender","year":"2004","unstructured":"Allender, E., Mahajan, M.: The complexity of planarity testing. Inf. Comput. 189, 117\u2013134 (2004)","journal-title":"Inf. Comput."},{"issue":"2","key":"9172_CR2","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1006\/jcss.1999.1646","volume":"59","author":"E. Allender","year":"1999","unstructured":"Allender, E., Reinhardt, K., Zhou, S.: Isolation, matching, and counting: Uniform and nonuniform upper bounds. J. Comput. Syst. Sci. 59(2), 164\u2013181 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9172_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/11590156_19","volume-title":"Proc. 25th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS)","author":"E. Allender","year":"2005","unstructured":"Allender, E., Datta, S., Roy, S.: The directed planar reachability problem. In: Proc. 25th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). Lecture Notes in Computer Science, vol. 1373, pp. 238\u2013249. Springer, Berlin (2005)"},{"key":"9172_CR4","doi-asserted-by":"crossref","unstructured":"Allender, E., Barrington, D.A.M., Chakraborty, T., Datta, S., Roy, S.: Grid graph reachability problems. In: IEEE Conference on Computational Complexity, pp. 299\u2013313 (2006)","DOI":"10.1109\/CCC.2006.22"},{"key":"9172_CR5","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D.A. Barrington","year":"1989","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38, 150\u2013164 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9172_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0028550","volume-title":"15th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"D.A.M. Barrington","year":"1998","unstructured":"Barrington, D.A.M., Lu, C.-J., Miltersen, P.B., Skyum, S.: Searching constant width mazes captures the AC0 hierarchy. In: 15th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 1373, pp. 73\u201383. Springer, Berlin (1998)"},{"key":"9172_CR7","doi-asserted-by":"crossref","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"9172_CR8","doi-asserted-by":"crossref","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous logspace. In: IEEE Conference on Computational Complexity, pp. 217\u2013221 (2007)","DOI":"10.1109\/CCC.2007.9"},{"key":"9172_CR9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/BF01271369","volume":"3","author":"H. Buhrman","year":"1993","unstructured":"Buhrman, H., Spaan, E., Torenvliet, L.: The relative power of logspace and polynomial time reductions. Comput. Complex. 3, 231\u2013244 (1993)","journal-title":"Comput. Complex."},{"key":"9172_CR10","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.tcs.2006.03.011","volume":"357","author":"S. Buss","year":"2006","unstructured":"Buss, S.: Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies. Theor. Comput. Sci. 357, 35\u201352 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9172_CR11","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0890-5401(91)90075-D","volume":"91","author":"S.R. Buss","year":"1991","unstructured":"Buss, S.R., Hay, L.: On truth-table reducibility to SAT. Inf. Comput. 91(1), 86\u2013102 (1991)","journal-title":"Inf. Comput."},{"issue":"4","key":"9172_CR12","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S.R. Buss","year":"1992","unstructured":"Buss, S.R., Cook, S., Gupta, A., Ramachandran, V.: An optimal parallel algorithm for formula evaluation. SIAM J. Comput. 21(4), 755\u2013780 (1992)","journal-title":"SIAM J. Comput."},{"key":"9172_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/11944836_8","volume-title":"Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS)","author":"T. Chakraborty","year":"2006","unstructured":"Chakraborty, T., Datta, S.: One-input-face MPCVP is hard for L, but in LogDCFL. In: Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS). Lecture Notes in Computer Science, vol. 4337, pp. 57\u201368. Springer, Berlin (2006)"},{"key":"9172_CR14","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S.A. Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space. J. Algorithms 8, 385\u2013394 (1987)","journal-title":"J. Algorithms"},{"key":"9172_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/978-3-540-74510-5_14","volume-title":"Computer Science\u2014Theory and Applications, Second International Symposium on Computer Science in Russia, (CSR 2007)","author":"S. Datta","year":"2007","unstructured":"Datta, S., Kulkarni, R., Limaye, N., Mahajan, M.: Planarity, determinants, permanents, and (unique) matchings. In: Computer Science\u2014Theory and Applications, Second International Symposium on Computer Science in Russia, (CSR 2007). Lecture Notes in Computer Science, vol. 4649, pp. 115\u2013126. Springer, Berlin (2007)"},{"issue":"1","key":"9172_CR16","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.R., Yung, M.: Maintenance of a minimum spanning forest in a dynamic planar graph. J. Algorithms 13(1), 33\u201354 (1992). (Corrigendum in vol. 15, 1993)","journal-title":"J. Algorithms"},{"issue":"3","key":"9172_CR17","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K. Etessami","year":"1997","unstructured":"Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. J. Comput. Syst. Sci. 54(3), 400\u2013411 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9172_CR18","volume-title":"Topological Graph Theory","author":"J. Gross","year":"1987","unstructured":"Gross, J., Tucker, T.: Topological Graph Theory, 1st edn. Wiley, New York (1987)","edition":"1"},{"key":"9172_CR19","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M., Radhakrishnan, J., Subrahmanyam, K.V.: Directed vs. undirected monotone contact networks for threshold functions. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 604\u2013613 (1993)","DOI":"10.1109\/SFCS.1993.366826"},{"issue":"1","key":"9172_CR20","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci. 55(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"9172_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/3-540-60313-1_144","volume-title":"Proc. 3rd ESA","author":"T. Husfeldt","year":"1995","unstructured":"Husfeldt, T.: Fully dynamic transitive closure in plane dags with one source and one sink. In: Proc. 3rd ESA. Lecture Notes in Computer Science, vol. 955, pp. 199\u2013212. Springer, Berlin (1995)"},{"issue":"4","key":"9172_CR22","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that capture complexity classes. SIAM J. Comput. 16(4), 760\u2013778 (1987)","journal-title":"SIAM J. Comput."},{"key":"9172_CR23","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman, N.: Nondeterministic space is closed under complementation. SIAM J. Comput. 17, 935\u2013938 (1988)","journal-title":"SIAM J. Comput."},{"key":"9172_CR24","series-title":"Springer Graduate Texts in Computer Science","volume-title":"Descriptive Complexity","author":"N. Immerman","year":"1998","unstructured":"Immerman, N.: Descriptive Complexity. Springer Graduate Texts in Computer Science. Springer, Berlin (1998)"},{"key":"9172_CR25","unstructured":"Jakoby, A., Tantau, T.: Personal communication (2006)"},{"key":"9172_CR26","doi-asserted-by":"crossref","unstructured":"Jakoby, A., Tantau, T.: Logspace algorithms for computing shortest and longest paths in series-parallel graphs. In: Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS), pp. 216\u2013227 (2007)","DOI":"10.1007\/978-3-540-77050-3_18"},{"key":"9172_CR27","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.jalgor.2004.06.010","volume":"60","author":"A. Jakoby","year":"2006","unstructured":"Jakoby, A., Liskiewicz, M., Reischuk, R.: Space efficient algorithms for directed series-parallel graphs. J. Algorithms 60, 85\u2013114 (2006)","journal-title":"J. Algorithms"},{"key":"9172_CR28","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01683260","volume":"10","author":"R. Ladner","year":"1976","unstructured":"Ladner, R., Lynch, N.: Relativization of questions about log space reducibility. Math. Syst. Theory 10, 19\u201332 (1976)","journal-title":"Math. Syst. Theory"},{"key":"9172_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/BFb0023471","volume-title":"14th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"K.-J. Lange","year":"1997","unstructured":"Lange, K.-J.: An unambiguous class possessing a complete set. In: 14th International Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 1200, pp. 339\u2013350. Springer, Berlin (1997)"},{"key":"9172_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1007\/11672142_54","volume-title":"Proc. 23rd Symposium on Theoretical Aspects of Computing (STACS)","author":"N. Limaye","year":"2006","unstructured":"Limaye, N., Mahajan, M., Sarma, J.M.N.: Evaluating monotone circuits on cylinders, planes, and torii. In: Proc. 23rd Symposium on Theoretical Aspects of Computing (STACS). Lecture Notes in Computer Science, pp. 660\u2013671. Springer, Berlin (2006)"},{"key":"9172_CR31","doi-asserted-by":"crossref","unstructured":"Mahajan, M., Varadarajan, K.R.: A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs. In: ACM Symposium on Theory of Computing (STOC), pp. 351\u2013357 (2000)","DOI":"10.1145\/335305.335346"},{"key":"9172_CR32","doi-asserted-by":"crossref","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B. Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces, 1st edn. John Hopkins University Press, Baltimore (2001)","edition":"1"},{"key":"9172_CR33","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ta-Shma, A.: Symmetric logspace is closed under complement. Chicago J. Theor. Comput. Sci. (1995)","DOI":"10.4086\/cjtcs.1995.001"},{"key":"9172_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/3-540-58950-3_385","volume-title":"Graph Drawing (GD94)","author":"A. Papakostas","year":"1995","unstructured":"Papakostas, A.: Upward planarity testing of outerplanar dags. In: Graph Drawing (GD94). Lecture Notes in Computer Science, vol. 894, pp. 298\u2013306. Springer, Berlin (1995)"},{"key":"9172_CR35","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected ST-connectivity in log-space. In: Proceedings of the 37th Symposium on Foundations of Computer Science, pp. 376\u2013385. IEEE Computer Society Press (2005)","DOI":"10.1145\/1060590.1060647"},{"key":"9172_CR36","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1137\/S0097539798339041","volume":"29","author":"K. Reinhardt","year":"2000","unstructured":"Reinhardt, K., Allender, E.: Making nondeterminism unambiguous. SIAM J. Comput. 29, 1118\u20131131 (2000)","journal-title":"SIAM J. Comput."},{"key":"9172_CR37","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcs\u00e9nyi","year":"1988","unstructured":"Szelepcs\u00e9nyi, R.: The method of forced enumeration for nondeterministic automata. Acta Inf. 26, 279\u2013284 (1988)","journal-title":"Acta Inf."},{"key":"9172_CR38","unstructured":"Thierauf, T., Wagner, F.: The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. In: 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp.\u00a0633\u2013644 (2008)"},{"issue":"2","key":"9172_CR39","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0095-8956(90)90115-G","volume":"48","author":"C. Thomassen","year":"1990","unstructured":"Thomassen, C.: Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory Ser. B 48(2), 155\u2013177 (1990)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9172_CR40","unstructured":"Yang, H.: An NC algorithm for the general planar monotone circuit value problem. In: SPDP: 3rd IEEE Symposium on Parallel and Distributed Processing. ACM Special Interest Group on Computer Architecture (SIGARCH) and IEEE Computer Society (1991)"},{"issue":"1","key":"9172_CR41","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/0022-0000(89)90032-9","volume":"38","author":"M. Yannakakis","year":"1989","unstructured":"Yannakakis, M.: Embedding planar graphs in four pages. J. Comput. Syst. Sci. 38(1), 36\u201367 (1989)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9172-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9172-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9172-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,10]],"date-time":"2024-03-10T01:34:05Z","timestamp":1710034445000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9172-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,5]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,11]]}},"alternative-id":["9172"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9172-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,5]]}}}