{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,7]],"date-time":"2026-06-07T08:49:11Z","timestamp":1780822151358,"version":"3.54.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,2,1]],"date-time":"2009-02-01T00:00:00Z","timestamp":1233446400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0430991"],"award-info":[{"award-number":["CCF-0430991"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2009,2]]},"abstract":"<jats:p>\n                    We make progress in understanding the complexity of the graph reachability problem in the context of unambiguous logarithmic space computation; a restricted form of nondeterminism. As our main result, we show a new upper bound on the\n                    <jats:italic toggle=\"yes\">directed planar reachability problem<\/jats:italic>\n                    by showing that it can be decided in the class unambiguous logarithmic space (UL). We explore the possibility of showing the same upper bound for the general graph reachability problem. We give a simple reduction showing that the reachability problem for directed graphs with thickness two is complete for the class nondeterministic logarithmic space (NL). Hence an extension of our results to directed graphs with thickness two will unconditionally collapse NL to UL.\n                  <\/jats:p>","DOI":"10.1145\/1490270.1490274","type":"journal-article","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T09:56:36Z","timestamp":1259574996000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Directed Planar Reachability Is in Unambiguous Log-Space"],"prefix":"10.1145","volume":"1","author":[{"given":"Chris","family":"Bourke","sequence":"first","affiliation":[{"name":"University of Nebraska--Lincoln"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghunath","family":"Tewari","sequence":"additional","affiliation":[{"name":"University of Nebraska--Lincoln"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska--Lincoln"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2009,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.22"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_19"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000102"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2003.09.002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1646"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646513.695505"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.30"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/647895.740454"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2391910.2391924"},{"key":"e_1_2_1_12_1","first-page":"229","volume-title":"Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science.","author":"Datta S.","unstructured":"Datta, S., Kulkarni, R., and Roy, S. 2008. Deterministically isolating a perfect matching in bipartite planar graphs. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science. pp. 229--240, www.stacs-conf.org."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00023"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1485"},{"key":"e_1_2_1_15_1","volume-title":"Algorithmic Graph Theory","author":"Gibbons A.","unstructured":"Gibbons, A. 1985. Algorithmic Graph Theory. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217018"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/647547.728616"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/646512.695352"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1862776.1862788"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060647"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798339041"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"},{"key":"e_1_2_1_25_1","first-page":"633","volume-title":"Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science","author":"Thierauf T.","unstructured":"Thierauf, T. and Wagner, F. 2008. The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, pp. 633--644, www.stacs-conf.org."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90097-1"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1490270.1490274","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1490270.1490274","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1490270.1490274","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:26:35Z","timestamp":1763457995000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1490270.1490274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,2]]}},"alternative-id":["10.1145\/1490270.1490274"],"URL":"https:\/\/doi.org\/10.1145\/1490270.1490274","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2]]},"assertion":[{"value":"2009-02-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}