0 votes

There exists very nice reduction of the bipartite perfect matching problem in planar graph to the shortest path problem in the dual graph. The reduction can be find in the paper by Miller and Naor: http://www.cs.cmu.edu/~glmiller/Publications/Papers/MillerNaor95.pdf. Combined with with the paper by Fakcharoenphol and Rao: http://www.cs.berkeley.edu/~satishr/negcycle.ps, or with the paper by Mozes and Wulff-Nilsen http://www.springerlink.com/content/p216876051k1kr61/ this gives an almost linear time algorithm for finding perfect matchings in biparite planar graphs. However, this interpretation is restricted only to bipartite graphs. Does similar reduction work for general planar graphs as well?