\chapter{Conclusion and Future Work}
\label{conclusion}
\markright{Mudabir Kabir Asathulla \hfill Chapter 5. Conclusion and Future Work \hfill}
\paragraph{}
We presented a $\sixfive$ algorithm for finding maximum cardinality matching in planar bipartite graphs. We achieved this using a sparsification based approach where we reduce the actual graph $G$ to a sparser graph $H$ comprising of just the boundary vertices from r-division and special internal vertices without losing information needed for matching. The edges in the sparser graph $H$ were constructed by maintaining dense distance graph (DDG) for each region of r-division. Motivated by FR-Dijkstra \cite{frao}, we came up with a faster algorithm for BFS and DFS which runs in time proportional to number of vertices in $H$ i.e. $O(n/\sqrt{r})$ instead of order of number of edges $O(n)$. We used a balanced value of $r$ to ensure that the graph is sparse enough and at the same time, each region has a small number of vertices. As future work, we believe that the sparsification approach introduced in this work can be extended to following problems.
\paragraph{Near Linear time Maximum Cardinality Matching in Bipartite Planar Graphs}
As stated before, our algorithm is not the fastest known solution. Borradaile et al. \cite{borradaile} showed that this problem can be solved in $O(n\log^{3}{n})$. Can the algorithm be improved to perform in near linear time if we could recompute induced internal edges in each region efficiently after augmentation? Currently, we compute all the edges in every region that the augmenting path goes through, but this is certainly an overkill.
\paragraph{Maximum Cardinality Matching in General Planar Graphs}
Most of the properties proved for our algorithm also extend to general (non bipartite) planar graphs. $O(n^{3/2})$ 
($O(n^{\omega})$ is fastest) is the best bound known so far for combinatorial algorithm for general matching in planar graphs, as a result of $O(m\sqrt{n})$ algorithm for arbitrary graphs by Micali and Vazirani \cite{micali1980},\cite{vazirani2012}. The complexity of general graph matching algorithms stems from the odd length alternating cycles which are absent in bipartite graphs. Nobert Blum \cite{blum1990},\cite{blum2015} talks about transforming general graph $G$ to a bipartite graph $G'$ and computing maximum matching by applying Hopcroft-Karp algorithm on $G'$. We need to verify if this reduction of general matching to bipartite matching along with our sparsification approach can help improve the complexity of general matching. 
\paragraph{Maximum Weighted Matching in Bipartite Planar Graphs}
At the time of this writing, it has been proved that the sparsification approach can be adapted in weighted setting and improvement to $\fourthree$ has been achieved. Again, just like $\fourthree$, $\sixfive$ or even near-linear time may also be possible in weighted matching, bridging the gap between the complexity of weighted and unweighted matching in planar bipartite graphs.
\paragraph{Approximate Bottleneck Matching}
Another important question is whether this sparsification approach can be extended to non-planar graphs which have sub-linear separator size. By using approximations and clustering, it is possible to reduce bottleneck matching problem to a sparse graph matching with vertices on grid centers. It remains to be seen if $\epsilon$-approximation for bottleneck matching on non-planar graphs is plausible with our sparsification approach.