Planarizing Gadgets for Perfect Matching Do Not Exist
Rohit Gurjar, Arpita Korwar, Jochen Meßner, Simon Straub, Thomas Thierauf · ACM Transactions on Computation Theory · 2016
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.