{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T19:33:15Z","timestamp":1776281595899,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,7,26]],"date-time":"2016-07-26T00:00:00Z","timestamp":1469491200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["TH 472\/4"],"award-info":[{"award-number":["TH 472\/4"]}],"id":[{"id":"10.13039\/501100001659","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":[[2016,7,26]]},"abstract":"<jats:p>To reduce a graph problem to its planar version, a standard technique is to replace crossings in a drawing of the input graph by planarizing gadgets. We show unconditionally that such a reduction is not possible for the perfect matching problem and also extend this to some other problems related to perfect matching. We further show that there is no planarizing gadget for the Hamiltonian cycle problem.<\/jats:p>","DOI":"10.1145\/2934310","type":"journal-article","created":{"date-parts":[[2016,7,26]],"date-time":"2016-07-26T13:27:29Z","timestamp":1469539649000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Planarizing Gadgets for Perfect Matching Do Not Exist"],"prefix":"10.1145","volume":"8","author":[{"given":"Rohit","family":"Gurjar","sequence":"first","affiliation":[{"name":"Indian Institute of Technology, Kanpur"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arpita","family":"Korwar","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Kanpur, Kanpur (UP), India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jochen","family":"Messner","sequence":"additional","affiliation":[{"name":"Aalen University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon","family":"Straub","sequence":"additional","affiliation":[{"name":"Ulm University, Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[{"name":"Aalen University, Aalen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,26]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Retrieved","author":"Burke K.","year":"2012","unstructured":"K. Burke . 2012 . Theoretical Computer Science Stack Exchange . Retrieved May 17, 2016, from http:\/\/cstheory. stackexchange.com\/questions\/9587. K. Burke. 2012. Theoretical Computer Science Stack Exchange. Retrieved May 17, 2016, from http:\/\/cstheory. stackexchange.com\/questions\/9587."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1046"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00006-7"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1714450.1714453"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9204-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1167"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205049"},{"key":"e_1_2_1_10_1","volume-title":"Computational Complexity Blog. Retrieved","author":"Gasarch W.","year":"2012","unstructured":"W. Gasarch . 2012 . Is there a NICE gadget for showing PLANAR HC is NPC ? Computational Complexity Blog. Retrieved May 17, 2016, from http:\/\/blog.computationalcomplexity.org\/2012\/01\/is-there-nice-gadget-for-showing-planar.html. W. Gasarch. 2012. Is there a NICE gadget for showing PLANAR HC is NPC? Computational Complexity Blog. Retrieved May 17, 2016, from http:\/\/blog.computationalcomplexity.org\/2012\/01\/is-there-nice-gadget-for-showing-planar.html."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_40"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.21"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_14_1","unstructured":"D. Johnson. 2012. Comment to: Is there a NICE gadget for showing PLANAR HC is NPC?Computational Complexity Blog. http:\/\/blog.computationalcomplexity.org\/2012\/01\/is-there-nice-gadget-for-showing-planar.html?showComment=1325864505803#c5063180797819792185. D. Johnson. 2012. Comment to: Is there a NICE gadget for showing PLANAR HC is NPC?Computational Complexity Blog. http:\/\/blog.computationalcomplexity.org\/2012\/01\/is-there-nice-gadget-for-showing-planar.html?showComment=1325864505803#c5063180797819792185."},{"key":"e_1_2_1_15_1","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","unstructured":"R. M. Karp . 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations , R. E. Miller, J. W. Thatcher, and J. D. Bohlinger (Eds.). Springer , 85--103. DOI:http:\/\/dx.doi.org\/ 10.1007\/978-1-4684-2001-2_9 10.1007\/978-1-4684-2001-2_9 R. M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller, J. W. Thatcher, and J. D. Bohlinger (Eds.). Springer, 85--103. DOI:http:\/\/dx.doi.org\/ 10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"M. Karpinski and W. Rytter. 1998. Fast Parallel Algorithms for Graph Matching Problems. Oxford University Press. M. Karpinski and W. Rytter. 1998. Fast Parallel Algorithms for Graph Matching Problems. Oxford University Press.","DOI":"10.1093\/oso\/9780198501626.001.0001"},{"key":"e_1_2_1_17_1","volume-title":"Academic Press","author":"Kasteleyn P. W.","unstructured":"P. W. Kasteleyn . 1967. Graph theory and crystal physics . In Graph Theory and Theoretical Physics, F. Harary (Ed.). Academic Press , Cambridge , MA , 43--110. P. W. Kasteleyn. 1967. Graph theory and crystal physics. In Graph Theory and Theoretical Physics, F. Harary (Ed.). Academic Press, Cambridge, MA, 43--110."},{"key":"e_1_2_1_18_1","volume-title":"The Design and Analysis of Algorithms","author":"Kozen D.","unstructured":"D. Kozen . 1991. The Design and Analysis of Algorithms . Springer . D. Kozen. 1991. The Design and Analysis of Algorithms. Springer."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 5th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201985)","author":"Kozen D. C.","unstructured":"D. C. Kozen , U. V. Vazirani , and V. V. Vazirani . 1985. NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matchings . In Proceedings of the 5th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201985) . Springer, 496--503. D. C. Kozen, U. V. Vazirani, and V. V. Vazirani. 1985. NC algorithms for comparability graphs, interval graphs, and testing for unique perfect matchings. In Proceedings of the 5th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201985). Springer, 496--503."},{"key":"e_1_2_1_20_1","unstructured":"R. Kulkarni M. Mahajan and K. Varadarajan. 2008. Some perfect matchings and perfect half-integral matchings in NC. Chicago Journal of Theoretical Computer Science 2008 Article No. 4. R. Kulkarni M. Mahajan and K. Varadarajan. 2008. Some perfect matchings and perfect half-integral matchings in NC. Chicago Journal of Theoretical Computer Science 2008 Article No. 4."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1963635.1963636"},{"key":"e_1_2_1_22_1","article-title":"Matching Theory","author":"Lovasz L.","year":"1986","unstructured":"L. Lovasz and M. D. Plummer . 1986 . Matching Theory . Annals of Discrete Mathematics. North-Holland. L. Lovasz and M. D. Plummer. 1986. Matching Theory. Annals of Discrete Mathematics. North-Holland.","journal-title":"Annals of Discrete Mathematics. North-Holland."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335346"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539789162997"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322309"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90017-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305952"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9519-0"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2934310","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2934310","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:54Z","timestamp":1750222494000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2934310"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,26]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,26]]}},"alternative-id":["10.1145\/2934310"],"URL":"https:\/\/doi.org\/10.1145\/2934310","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,7,26]]},"assertion":[{"value":"2014-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}