Planarizing Gadgets for Perfect Matching do not Exist

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem. The obvious way to construct such a reduction is via a planarizing gadget, a planar graph which replaces all edge crossings of a given graph. We show that no such gadget exists. This provides a further indication that the complexity of the two problems is different.