A Sparsification Based Algorithm for Maximum-Cardinality Bipartite Matching in Planar Graphs

Abstract

Matching is one of the most fundamental algorithmic graph problems. Many variants of matching problems have been studied on different classes of graphs, the one of special interest to us being the Maximum Cardinality Bipartite Matching in Planar Graphs. In this work, we present a novel sparsification based approach for computing maximum/perfect bipartite matching in planar graphs. The overall complexity of our algorithm is O(n6/5 log² n) where n is the number of vertices in the graph, bettering the O(n3/2) time achieved independently by Hopcroft-Karp algorithm and by Lipton and Tarjan divide and conquer approach using planar separators. Our algorithm combines the best of both these standard algorithms along with our sparsification technique and rich planar graph properties to achieve the speed up. Our algorithm is not the fastest, with the existence of O(n log³ n) algorithm based on max-flow reduction.