Welcome to Fnd2012 Open Problems, where you can ask questions and receive answers from other members of the community.

Does there exists a dual combinatorial interpretation of the matching problem in planar graphs?

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?

asked Jul 31, 2012 by sank (180 points)