Advertisement
Published in:
2012 | OriginalPaper | Chapter
Planarizing Gadgets for Perfect Matching Do Not Exist
Authors : Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf
Published in: Mathematical Foundations of Computer Science 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.