{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:43:08Z","timestamp":1770903788431,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,6,4]],"date-time":"2022-06-04T00:00:00Z","timestamp":1654300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,4]],"date-time":"2022-06-04T00:00:00Z","timestamp":1654300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1909216"],"award-info":[{"award-number":["CCF-1909216"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1909683"],"award-info":[{"award-number":["CCF-1909683"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]},{"name":"SERB-MATRICS","award":["MTR\/2017\/000480"],"award-info":[{"award-number":["MTR\/2017\/000480"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00236-022-00425-1","type":"journal-article","created":{"date-parts":[[2022,6,4]],"date-time":"2022-06-04T16:02:30Z","timestamp":1654358550000},"page":"289-319","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Depth-first search in directed planar graphs, revisited"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0650-028X","authenticated-orcid":false,"given":"Eric","family":"Allender","sequence":"first","affiliation":[]},{"given":"Archit","family":"Chauhan","sequence":"additional","affiliation":[]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,4]]},"reference":[{"issue":"2","key":"425_CR1","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0219025","volume":"19","author":"A Aggarwal","year":"1990","unstructured":"Aggarwal, A., Anderson, R.J., Kao, M.-Y.: Parallel depth-first search in general directed graphs. SIAM J. Comput. 19(2), 397\u2013409 (1990). https:\/\/doi.org\/10.1137\/0219025","journal-title":"SIAM J. Comput."},{"issue":"4","key":"425_CR2","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/s00224-009-9172-z","volume":"45","author":"E Allender","year":"2009","unstructured":"Allender, E., Barrington, D.A.M., Chakraborty, T., Datta, S., Roy, S.: Planar and grid graph reachability problems. Theory Comput. Syst. 45(4), 675\u2013723 (2009). https:\/\/doi.org\/10.1007\/s00224-009-9172-z","journal-title":"Theory Comput. Syst."},{"key":"425_CR3","unstructured":"Allender, E., Chauhan, A., Datta, S.: Depth-first search in directed graphs, revisited. Technical report TR20-074, Electronic Colloquium on Computational Complexity (ECCC) (2020)"},{"key":"425_CR4","first-page":"39","volume":"26","author":"E Allender","year":"2019","unstructured":"Allender, E., Chauhan, A., Datta, S., Mukherjee, A.: Planarity, exclusivity, and unambiguity. Electron. Colloq. Comput. Complex. ECCC 26, 39 (2019)","journal-title":"Electron. Colloq. Comput. Complex. ECCC"},{"issue":"5","key":"425_CR5","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s002240000102","volume":"31","author":"E Allender","year":"1998","unstructured":"Allender, E., Lange, K.-J.: $$ RUSPACE(\\log n) \\subseteq DSPACE (\\log ^2 n\/\\log \\log n)$$. Theory Comput. Syst. 31(5), 539\u2013550 (1998). https:\/\/doi.org\/10.1007\/s002240000102","journal-title":"Theory Comput. Syst."},{"key":"425_CR6","doi-asserted-by":"publisher","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":"425_CR7","doi-asserted-by":"publisher","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":"425_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity, a Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity, a Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"425_CR9","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/978-3-319-13075-0_44","volume-title":"Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), volume 8889 of Lecture Notes in Computer Science","author":"T Asano","year":"2014","unstructured":"Asano, T., Izumi, T., Kiyomi, M., Konagaya, M., Ono, H., Otachi, Y., Schweitzer, P., Tarui, J., Uehara, R.: Depth-first search using $${O}(n)$$ bits. In: Ahn, H.-K., Shin, C.-S. (eds.) Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC), volume 8889 of Lecture Notes in Computer Science, pp. 553\u2013564. Springer, New York (2014). https:\/\/doi.org\/10.1007\/978-3-319-13075-0_44"},{"key":"425_CR10","volume-title":"Graph Drawing: Algorithms for the Visualization of Graphs","author":"G Di Battista","year":"1998","unstructured":"Di Battista, G., Eades, P., Tamassiao, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, Hoboken (1998)"},{"issue":"2","key":"425_CR11","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/1502793.1502798","volume":"56","author":"G Borradaile","year":"2009","unstructured":"Borradaile, G., Klein, P.N.: An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM 56(2), 9:1-9:30 (2009). https:\/\/doi.org\/10.1145\/1502793.1502798","journal-title":"J. ACM"},{"issue":"1","key":"425_CR12","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/1490270.1490274","volume":"1","author":"C Bourke","year":"2009","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous log-space. TOCT 1(1), 4:1-4:17 (2009). https:\/\/doi.org\/10.1145\/1490270.1490274","journal-title":"TOCT"},{"key":"425_CR13","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1007\/3-540-54458-5_61","volume-title":"Proceedings 8th Symposium on Fundamentals of Computation Theory (FCT), volume 529 of Lecture Notes in Computer Science","author":"G Buntrock","year":"1991","unstructured":"Buntrock, G., Jenner, B., Lange, K.-J., Rossmanith, P.: Unambiguity and fewness for logarithmic space. In: Budach, L. (ed.) Proceedings 8th Symposium on Fundamentals of Computation Theory (FCT), volume 529 of Lecture Notes in Computer Science, pp. 168\u2013179. Springer, New York (1991). https:\/\/doi.org\/10.1007\/3-540-54458-5_61"},{"key":"425_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, 1st edn. Springer, New York (2015)","edition":"1"},{"key":"425_CR15","doi-asserted-by":"publisher","unstructured":"Datta, S., Limaye, N., Nimbhorkar, P., Thierauf, T., Wagner, F.: Planar graph isomorphism is in log-space. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC), pp. 203\u2013214 (2009). https:\/\/doi.org\/10.1109\/CCC.2009.16","DOI":"10.1109\/CCC.2009.16"},{"issue":"1","key":"425_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.1995.1025","volume":"19","author":"P de la Torre","year":"1995","unstructured":"de la Torre, P., Kruskal, C.P.: Fast parallel algorithms for all-sources lexicographic search and path-algebra problems. J. Algorithms 19(1), 1\u201324 (1995). https:\/\/doi.org\/10.1006\/jagm.1995.1025","journal-title":"J. Algorithms"},{"issue":"4","key":"425_CR17","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00224-001-1008-4","volume":"34","author":"P de la Torre","year":"2001","unstructured":"de la Torre, P., Kruskal, C.P.: Polynomially improved efficiency for fast parallel single-source lexicographic depth-first search, breadth-first search, and topological-first search. Theory Comput. Syst. 34(4), 275\u2013298 (2001). https:\/\/doi.org\/10.1007\/s00224-001-1008-4","journal-title":"Theory Comput. Syst."},{"key":"425_CR18","volume-title":"Graph Theory, Volume 173 of Graduate Texts in Mathematics","author":"R Diestel","year":"2016","unstructured":"Diestel, R.: Graph Theory, Volume 173 of Graduate Texts in Mathematics. Springer, New York (2016)"},{"key":"425_CR19","doi-asserted-by":"publisher","unstructured":"Elmasry, A., Hagerup, T., Kammer, F.: Space-efficient basic graph algorithms. In: Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), volume 30 of LIPIcs, pp. 288\u2013301. Schloss Dagstuhl - Leibniz-Zentrum fur Informatik (2015). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2015.288","DOI":"10.4230\/LIPIcs.STACS.2015.288"},{"key":"425_CR20","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/3-540-62034-6_57","volume-title":"16th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 1180 of Lecture Notes in Computer Science","author":"H Fernau","year":"1996","unstructured":"Fernau, H., Lange, K.-J., Reinhardt, K.: Advocating ownership. In: Chandru, V., Vinay, V. (eds.) 16th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), volume 1180 of Lecture Notes in Computer Science, pp. 286\u2013297. Springer, New York (1996). https:\/\/doi.org\/10.1007\/3-540-62034-6_57"},{"issue":"4","key":"425_CR21","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/0219047","volume":"19","author":"T Hagerup","year":"1990","unstructured":"Hagerup, T.: Planar depth-first search in O(log $$n$$) parallel time. SIAM J. Comput. 19(4), 678\u2013704 (1990). https:\/\/doi.org\/10.1137\/0219047","journal-title":"SIAM J. Comput."},{"issue":"4","key":"425_CR22","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1007\/s00453-019-00629-x","volume":"82","author":"T Hagerup","year":"2020","unstructured":"Hagerup, T.: Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster. Algorithmica 82(4), 1033\u20131056 (2020). https:\/\/doi.org\/10.1007\/s00453-019-00629-x","journal-title":"Algorithmica"},{"key":"425_CR23","doi-asserted-by":"publisher","unstructured":"Izumi, T., Otachi, Y.: Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs. In Czumaj, A., Dawar, A., Merelli, E. (eds.), Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP), volume 168 of LIPIcs, pp. 67:1\u201367:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.67","DOI":"10.4230\/LIPIcs.ICALP.2020.67"},{"key":"425_CR24","unstructured":"Jenner, B., Kirsig, B.: Alternierung und Logarithmischer Platz. Dissertation, Universit\u00e4t Hamburg (1989)"},{"issue":"3","key":"425_CR25","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0890-5401(89)90012-6","volume":"80","author":"B Jenner","year":"1989","unstructured":"Jenner, B., Kirsig, B., Lange, K.-J.: The logarithmic alternation hierarchy collapses: a $$2^l$$ = a$$\\pi _2^l$$. Inf. Comput. 80(3), 269\u2013287 (1989). https:\/\/doi.org\/10.1016\/0890-5401(89)90012-6","journal-title":"Inf. Comput."},{"issue":"3","key":"425_CR26","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0222032","volume":"22","author":"M-Y Kao","year":"1993","unstructured":"Kao, M.-Y.: Linear-processor NC algorithms for planar directed graphs I: strongly connected components. SIAM J. Comput. 22(3), 431\u2013459 (1993). https:\/\/doi.org\/10.1137\/0222032","journal-title":"SIAM J. Comput."},{"issue":"1","key":"425_CR27","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1137\/S0097539792227077","volume":"24","author":"M-Y Kao","year":"1995","unstructured":"Kao, M.-Y.: Planar strong connectivity helps in parallel depth-first search. SIAM J. Comput. 24(1), 46\u201362 (1995). https:\/\/doi.org\/10.1137\/S0097539792227077","journal-title":"SIAM J. Comput."},{"issue":"3","key":"425_CR28","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1016\/0022-0000(93)90042-U","volume":"47","author":"M-Y Kao","year":"1993","unstructured":"Kao, M.-Y., Klein, P.N.: Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs. J. Comput. Syst. Sci. 47(3), 459\u2013500 (1993). https:\/\/doi.org\/10.1016\/0022-0000(93)90042-U","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"425_CR29","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/s00453-010-9436-7","volume":"61","author":"H Kaplan","year":"2011","unstructured":"Kaplan, H., Nussbaum, Y.: Maximum flow in directed planar graphs with vertex capacities. Algorithmica 61(1), 174\u2013189 (2011). https:\/\/doi.org\/10.1007\/s00453-010-9436-7","journal-title":"Algorithmica"},{"issue":"1","key":"425_CR30","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(93)90255-R","volume":"107","author":"K-J Lange","year":"1993","unstructured":"Lange, K.-J.: Unambiguity of circuits. Theor. Comput. Sci. 107(1), 77\u201394 (1993). https:\/\/doi.org\/10.1016\/0304-3975(93)90255-R","journal-title":"Theor. Comput. Sci."},{"key":"425_CR31","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BFb0023471","volume-title":"14th Annual Symposium on Theoretical Aspects of Computer (STACS), volume 1200 of Lecture Notes in Computer Science","author":"K-J Lange","year":"1997","unstructured":"Lange, K.-J.: An unambiguous class possessing a complete set. In: Reischuk, R., Morvan, M. (eds.) 14th Annual Symposium on Theoretical Aspects of Computer (STACS), volume 1200 of Lecture Notes in Computer Science, pp. 339\u2013350. Springer, New York (1997). https:\/\/doi.org\/10.1007\/BFb0023471"},{"key":"425_CR32","doi-asserted-by":"publisher","unstructured":"Lange, K.-J., Rossmanith, P.: Characterizing unambiguous augmented pushdown automata by circuits. In: Rovan, B. (ed.), Proceedings of the Mathematical Foundations of Computer Science (MFCS), volume 452 of Lecture Notes in Computer Science, pp. 399\u2013406. Springer (1990). https:\/\/doi.org\/10.1007\/BFb0029635","DOI":"10.1007\/BFb0029635"},{"key":"425_CR33","doi-asserted-by":"publisher","unstructured":"Naumov, M., Vrielink, A., Garland, M.: Parallel depth-first search for directed acyclic graphs. In: Proceedings of the 7th Workshop on Irregular Applications: Architectures and Algorithms, pp. 4:1\u20134:8 (2017). https:\/\/doi.org\/10.1145\/3149704.3149764","DOI":"10.1145\/3149704.3149764"},{"issue":"5","key":"425_CR34","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0020-0190(85)90024-9","volume":"20","author":"HR John","year":"1985","unstructured":"John, H.R.: Depth-first search is inherently sequential. Inf. Process. Lett. 20(5), 229\u2013234 (1985). https:\/\/doi.org\/10.1016\/0020-0190(85)90024-9","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"425_CR35","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 45 (2008)","journal-title":"J. ACM"},{"issue":"4","key":"425_CR36","doi-asserted-by":"publisher","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(4), 1118\u20131131 (2000). https:\/\/doi.org\/10.1137\/S0097539798339041","journal-title":"SIAM J. Comput."},{"issue":"2","key":"425_CR37","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00224-007-2011-1","volume":"41","author":"T Tantau","year":"2007","unstructured":"Tantau, T.: Logspace optimization problems and their approximability properties. Theory Comput. Syst. 41(2), 327\u2013350 (2007). https:\/\/doi.org\/10.1007\/s00224-007-2011-1","journal-title":"Theory Comput. Syst."},{"key":"425_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2012.03.002","volume":"215","author":"R Tewari","year":"2012","unstructured":"Tewari, R., Vinodchandran, N.V.: Green\u2019s theorem and isolation in planar graphs. Inf. Comput. 215, 1\u20137 (2012). https:\/\/doi.org\/10.1016\/j.ic.2012.03.002","journal-title":"Inf. Comput."},{"issue":"3","key":"425_CR39","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s00224-009-9188-4","volume":"47","author":"T Thierauf","year":"2010","unstructured":"Thierauf, T., Wagner, F.: The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory Comput. Syst. 47(3), 655\u2013673 (2010). https:\/\/doi.org\/10.1007\/s00224-009-9188-4","journal-title":"Theory Comput. Syst."},{"issue":"2","key":"425_CR40","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(75)90032-1","volume":"12","author":"WT Tutte","year":"1975","unstructured":"Tutte, W.T.: Separation of vertices by a circuit. Discrete Math. 12(2), 173\u2013184 (1975)","journal-title":"Discrete Math."},{"key":"425_CR41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"H Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, New York (1999). https:\/\/doi.org\/10.1007\/978-3-662-03927-4"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00425-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00425-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00425-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:07:39Z","timestamp":1661591259000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00425-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,4]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["425"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00425-1","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,4]]},"assertion":[{"value":"14 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}