Planarizing Gadgets for Perfect Matching do not Exist!

At Dagstuhl I was delighted when I saw the title of a talk to be given Planarizing Gadgets for Perfect Matching do not Exist because I had asked the question about a gadget for planar Ham Cycle here. I was hoping to ask the authors if there techniques could be used to show that there was not Planarizing gadget for Ham Cycle (NOTE- I had either forgot or never knew that this was already known and was posted as an answer to my query to cstheory stackexchange, here.)

The paper Planarizing Gadgets for Perfect Matching do not Exist (or if you can get to it the MFCS 2012 version here) is by Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf. The talk was given by Jochen and was excellent.

Perfect matching is in P (Edmonds 1965) but is it in NC? Not known--- however it is in RNC (Mulmuley, Vazirani, Vazirani 1987). What about Planar graphs? They are different--- counting the number of perfect matching in a graph is Sharp-P complete (Valiant 1979) but counting the number of perfect matchings in a planar graph is in NC (Vazirani 1989). So of course Planar Graph Matching is in NC. Can we use this to get Graph Matching in NC? perhaps be a reduction? This would be neat since we would be using a reduction to prove a problem EASY rather than to prove a problem HARD. (I think this has been done before but is rare-- readers, if you know a case comment on it.) Perhaps there is some planarizing gadget: given a graph G use some gadgets to get rid of crossings and produce a planar graph G' such that G has a perfect matching iff G' has a perfect matching. That would be AWESOME! However, from the very title of the paper, we can guess this is not true. This paper shows that something AWESOME is not possible! A downer but worth knowing.

Jochen proved this and then went on to say that they had done the same thing for HAM CYCLE! That is, there is no planarization gadget for Ham cycle! (He also acknowledged that this was already known independently.) SO I didn't get to ask my question since they already had answered it. Great!

1. Their interest in planarization was related to an OPEN problem--- is Graph Matching in NC? By contrast my interest in Planarization gadgets for Ham Cycle was pedagogical--- I was in search of a better proof that Planar Ham Cycle is NPC- though there is no new theorem here.
   
2. I am delighted to know the result!
   
3. Their results says that a certain type of reduction won't work. Might some other reduction work? My sense is this is unlikely.
   
4. So--- is Graph Matching in NC? Since I believe NC=RNC I think yes. Will it be proven by showing NC=RNC or will it be proven directly (leaving NC=RNC open)? Or will the ideas that lead to Graph Matching in NC help to show NC=RNC? This is one of those questions that might be solved within a decade, as opposed to P vs NP which won't be resolved for quite some time.