{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:02Z","timestamp":1750307162542,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,8,1]],"date-time":"2011-08-01T00:00:00Z","timestamp":1312156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2011,8]]},"abstract":"<jats:p>\n            We study (deterministic) isolation for certain structures in directed and undirected planar graphs. The motivation for undertaking such a study comes from recent positive results on this topic. For example: Bourke et al. [2009] isolate a directed path in planar graphs and subsequently Datta et al. [2010b] isolate a perfect matching in bipartite planar graphs. Our first observation is that sufficiently strong (and plausible) isolations for certain structures in planar graphs would have strong consequences such as:\n            <jats:italic>NL<\/jats:italic>\n            \u2286 \u2295\n            <jats:italic>L<\/jats:italic>\n            , Bipartite-Matching \u2208\n            <jats:italic>NC<\/jats:italic>\n            , and\n            <jats:italic>NP<\/jats:italic>\n            \u2286 \u2295\n            <jats:italic>P<\/jats:italic>\n            . Our second observation is that although we do not yet have such strong isolations for arbitrary planar graphs, we do have them for bipartite planar graphs, that is,\n            <jats:italic>non-bipartiteness<\/jats:italic>\n            is the main bottleneck.\n          <\/jats:p>","DOI":"10.1145\/2003685.2003687","type":"journal-article","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:30:18Z","timestamp":1314711018000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Power of Isolation in Planar Graphs"],"prefix":"10.1145","volume":"3","author":[{"given":"Raghav","family":"Kulkarni","sequence":"first","affiliation":[{"name":"LIAFA Paris 7 and LRI Paris 11"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of Babados Workshop on Computational Complexity. Lecture 9.","author":"Agrawal M.","year":"2007","unstructured":"Agrawal , M. 2007 . Rings and integer lattices in computer science . In Proceedings of Babados Workshop on Computational Complexity. Lecture 9. Agrawal, M. 2007. Rings and integer lattices in computer science. In Proceedings of Babados Workshop on Computational Complexity. Lecture 9."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1646"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_19"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.22"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490274"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1714450.1714453"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9204-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2%3C99::AID-RSA7%3E3.0.CO;2-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205049"},{"volume-title":"Graph Theory and Theoretical Physics","author":"Kasteleyn P.","key":"e_1_2_1_10_1","unstructured":"Kasteleyn , P. 2011. Graph theory and crystal physics . In Graph Theory and Theoretical Physics . Academic Press , New York , 43--110. Kasteleyn, P. 2011. Graph theory and crystal physics. In Graph Theory and Theoretical Physics. Academic Press, New York, 43--110."},{"key":"e_1_2_1_11_1","unstructured":"Limaye N. Mahajan M. and Nimbhorkar P. 2008. Longest paths in planar dags in unambiguous log-space. CoRR abs\/0802.1699: (2008). Limaye N. Mahajan M. and Nimbhorkar P. 2008. Longest paths in planar dags in unambiguous log-space. CoRR abs\/0802.1699: (2008)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335346"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789162997"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_15_1","unstructured":"Tewari R. and Vinodchandran N. 2010. Green\u2019s theorem and isolation in planar graphs. Tech. rep. ECCC. Tewari R. and Vinodchandran N. 2010. Green\u2019s theorem and isolation in planar graphs. Tech. rep. ECCC."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/22101.22108"},{"volume-title":"Introduction to Circuit Complexity - A Uniform Approach : Texts in Theoretical Computer Science","author":"Vollmer H.","key":"e_1_2_1_17_1","unstructured":"Vollmer , H. 1999. Introduction to Circuit Complexity - A Uniform Approach : Texts in Theoretical Computer Science . Springer . Vollmer, H. 1999. Introduction to Circuit Complexity - A Uniform Approach : Texts in Theoretical Computer Science. Springer."},{"key":"e_1_2_1_18_1","series-title":"Lecture Notes in Computer Science","volume-title":"Alternating cycle covers and paths","author":"Vornberger O.","unstructured":"Vornberger , O. 1981. Alternating cycle covers and paths . Lecture Notes in Computer Science . vol. 100 . Vornberger, O. 1981. Alternating cycle covers and paths. Lecture Notes in Computer Science. vol. 100."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2003685.2003687","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2003685.2003687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:32Z","timestamp":1750240472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2003685.2003687"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["10.1145\/2003685.2003687"],"URL":"https:\/\/doi.org\/10.1145\/2003685.2003687","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2011,8]]},"assertion":[{"value":"2009-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}