\chapter{Improved Merge Algorithm}
\label{chapter4}
\markright{Mudabir Kabir Asathulla \hfill Chapter 4. Improved Merge Algorithm \hfill}
\paragraph{}
In this chapter, we present faster BFS and FINDAUGPATH (DFS) implementations which run in $\nbyr$ time instead of $O(n)$. Integrating these faster BFS and DFS along with the right choice of $r$ for \textit{r-division}, we show an improvement in the overall run time of our matching algorithm. First, we justify the choices of $r$ for the three versions of our matching algorithm. The first version is $\fourthree$ discussed in Chapter $\ref{chapter3}$. Second and third versions are presented in this chapter. In section \ref{FastBFS}, we show $\fivefour$ convergence by using just the faster BFS implementation and choosing $r=\sqrt{n}$. In section \ref{FastDFS}, we combine faster implementations of both BFS and DFS and fix $r=n^{2/5}$ to achieve $\sixfive$ matching algorithm. 
\section{Choice of r}
\label{choice}
\paragraph{}
There are two competing factors which affect the overall complexity of our matching algorithm. They are
\begin{itemize}
   \item Recomputing the edges of affected regions in $H$ after an augmentation: In Lemma \ref{delta}, we bounded the total length of all augmenting paths to be $$\Delta = \sum_{\PH \in \mathbb{P}} |\PH| = O(|V_H|\log{n})$$ where $V_H$ is $O(n/\sqrt{r})$. This is also the bound on number of times we recompute edges in a region. Time taken to recompute edges per region using DDG is $O(r\log^{3}{r})$. Therefore, the overall cost of this step over the entire run of the algorithm is $O(n\sqrt{r}\log^{4}{n})$. Note that computing maximum matching in all regions as a preprocessing step to eliminate augmenting paths within a region takes time $O(n\sqrt{r})$ in total and has the same bounds as recomputing the edges (ignoring the poly(log) term).
   \item Number of iterations and complexity of BFS/DFS: Number of iterations of algorithm is $O(\sqrt{V_H})$ as shown in Lemma \ref{lem:iterations}. Complexity of Standard BFS/DFS is $O(n)$ which is the number of edges in $H$. In this chapter, we improve BFS and DFS to run in time $O((n/\sqrt{r})\log^{2}{n})$ which is proportional to the number of vertices in $H$. Overall complexity of all the BFS/DFS operations would be $O(n^{3/2}/{r}^{1/4})$ with standard BFS/DFS and ${\overset{\sim}{O}(n^{3/2}/{r}^{3/4})}$ with improved BFS/DFS.
\end{itemize}
Ignoring the polylog terms and equating the complexity of above 2 operations, we get 3 cases.
\paragraph{Case 1: Using Standard BFS/DFS}
\[n\sqrt{r} = (n^{3/2}/{r}^{1/4}) \rightarrow r = n^{2/3} \]This gives an overall complexity of $\fourthree$.
\paragraph{Case 2: Using Improved BFS}
Since we are using 'divide and conquer' approach for computing maximum matching, there are at most $O(\sqrt{n})$ unmatched vertices in the merge step at the topmost level. Even if we find just one augmenting path per iteration, we need $O(\sqrt{n})$ iterations. Therefore, in this case, we use just the improved BFS. Now comparing the two factors discussed above, we have 
\[n\sqrt{r} = (n^{3/2}/\sqrt{r}) \rightarrow r = \sqrt{n} \]
This gives an overall complexity of $\fivefour$.
\paragraph{Case 3: Using Improved BFS+DFS}
Here the number of iterations is $O(\sqrt{V_H})$ just like in Case 1. Equating the two factors gives us
\[n\sqrt{r} = (n^{3/2}/{r}^{3/4}) \rightarrow r = n^{2/5} \]
The overall complexity of our algorithm reduces to $\sixfive$.



\section{Faster BFS}
\label{FastBFS}
\subsection{Algorithm Overview}
 BFS can be seen as Dijkstra's algorithm with unit/equal edge costs. Our Faster BFS algorithm is similar to the one presented in \cite{kaplan2012submatrix} except that we deal with only unit/equal edge costs. The algorithm contains three steps.
 \begin{itemize}
 \item In the first step, all free internal vertices $b_j$ are assigned layer number $0$. 
 \item In the second step, we execute an implementation of Dijkstra's  called FR-Dijkstra given by Fakcharoenphol and Rao \cite{frao} which uses bipartite groups and range-minimum query data structures. Before starting FR-Dijkstra's, we assign all free boundary vertices in $\HSet{B}{F}$ with label $0$ in each bipartite Monge group $(X,Y)$ where these vertices appear in $Y$. We also assign all the neighbors of free internal vertices $b_j$, a label $1$ in the respective Monge groups containing them on $Y$ side. FR-Dijkstra efficiently computes the next edge to add to the BFS Layered graph thus assigning layer numbers to vertices. See section \ref{DDG Intro} for description of FR-Dijkstra. For detailed analysis, see \cite{frao} or section 5.2 of \cite{kaplan2012submatrix}. This step takes $O((n/\sqrt{r})\log^2{n}$ time in total. 
 \item In the third step, we set the layer number of free internal vertex $a_j$ as $L(a_j) = min_{\bigcup \RH{j},(u,a_j) \in \Ej} L(u) +1$. Since there are at most $O(n/\sqrt{r})$ vertices of type $(u,a_j)$, this step takes $O(n/\sqrt{r})$ time.
 \end{itemize}
 
 Implementation details with pseudo code is provided in section \ref{implementationBFS}. 
 \subsection{Algorithm Implementation}
 \label{implementationBFS}
\paragraph{}
We now present our FR-Dijkstra adaptation to do BFS on $H$. By our construction, the dense distance graph per region captures only the connectivity between the boundary vertices of the region. As stated before, FR-Dijkstra based BFS (FastBFS) achieves speedup by executing in time proportional to the number of boundary vertices which is $O(n/\sqrt{r})$ while the number of edges between boundary vertices in DDG could be $O(n)$. In addition to this, FastBFS also handles the edges in $H$ of type $(b_j,\K_j)$ and $(\K_j,a_j)$ exclusively in our algorithm which are at most $O(n/\sqrt{r})$ in number. The edge weights are neglected in DDGs and all the edges are considered to have equal weight. 
\begin{algorithm}[H]
\caption{BFS Using FR-Dijkstra}\label{alg:BFS}
\begin{algorithmic}[1]
\Procedure{FastBFS}{$H$}
\State $\forall$ $v \in H$, $\layer{v}= \infty$, $LastLayer= -1$, $S(visited) = \emptyset$
\For{ $v \in \bigcup_j \K_j \cap \HSet{B}{F}$}\Comment{Free boundary vertices of type B}\label{Initial1}
%\State $\layer{v}\gets 0$
\For{each $(X,Y) \in H$  s.t. $v \in Y$}
\If{$(X,Y)$ heap is empty}
\State $\Queue.INSERT((X,Y),0)$
\EndIf
\State $(X,Y).INSERT(v,0)$
%\State $\Queue.INSERT((X,Y),0, True)$
\EndFor
\EndFor
\For{ $v \in \bigcup_j b_j$}\Comment{Free internal vertices of type B}\label{Initial2}
\State $\layer{v}\gets 0$
\EndFor
\For{ $u \in \bigcup_j \N{v}{j}$ where $v \in \bigcup_j b_j $}
%\State $\layer{u}\gets 1$
\For{each $(X,Y) \in H$  s.t. $u \in Y$}
\If{$(X,Y)$ heap is empty}
\State $\Queue.INSERT((X,Y),1)$
\EndIf
\State $(X,Y).INSERT(u,1)$
\EndFor
\EndFor
%\algstore{myalg}
%\end{algorithmic}
%\end{algorithm}



%\begin{algorithm}                     
%\begin{algorithmic} [1]                   % enter the algorithmic environment
%\algrestore{myalg}
\While{$!\Queue$.EMPTY()}
\State $(X,Y) \gets \Queue.EXTRACTMIN()$
\State u $\gets$ (X,Y).EXTRACTMIN(Y$\backslash$ M)
\If{$u \not\in S$}\Comment{u is being visited for the first time}
\State $L(u) = d(u)$
\If{$L(u)$ == $LastLayer$}\label{if1}
\State \textbf{continue}\Comment{Dont activate next layer vertices}
\EndIf
\For{each $(X^{'},Y^{'})$ s.t $u \in X^{'}$}\Comment{relax edges in DDGs}\label{DDG}
\State $(X^{'},Y^{'})$.ACTIVATE($u,d(u)$)
\State $v \gets (X^{'},Y^{'})$.FINDMIN($Y^{'}\backslash M^{'}$)
\State $\Queue$.UPDATE$((X^{'},Y^{'}),d(v))$
\If{$v$ is free vertex and $(LastLayer == -1)$}\label{free}
\State $LastLayer = d(v)$
\EndIf
\EndFor
\For{each edge $(u,v)$ where $v \in \bigcup_j a_j$}\Comment{relax edges of type $(\K_j,a_j)$}\label{type3}
\State $L(v)=L(u)+1$
\State $LastLayer = d(v)$
\EndFor
\State $S= S \cup \{u\}$
%\EndIf
\Else
\State $v \gets (X,Y)$.FINDMIN($Y\backslash M$)
\State $\Queue$.UPDATE($(X,Y),d(v))$

\EndIf
\EndWhile
\State \textbf{return}
\EndProcedure
\end{algorithmic}
\end{algorithm}
\paragraph{}
Pseudo code for FastBFS is shown in Algorithm 2. FastBFS runs on $H$. Initially, all vertices in $H$ have $L(v) = \infty$ and $S$ which maintains the set of visited vertices is $\emptyset$. ACTIVATE, FINDMIN and EXTRACTMIN have the same function as described in section \ref{mongeheaps}. Note that we have eliminated all edges $(b_j,a_j)$ by finding maximum matching in each region during the preprocessing step. We use a global heap (Queue would suffice for BFS) $\Queue$ apart from local heaps for each bipartite Monge group $(X,Y)$. 
\paragraph{}
Line \ref{Initial1} adds all free boundary vertices of type $\K_j \cap \HSet{B}{F}$ to the local heaps of Monge groups that they are part of, with a distance label of 0. Each Monge group $(X,Y)$ has at most one representative in the global heap $\Queue$ which is the smallest distance label for a vertex in $Y/M$. We do the same for boundary vertices which are directly connected to any $v \in \bigcup_j b_j$ as shown in nested $\textit{for}$ loop starting in line \ref{Initial2}. In the while loop, we extract the smallest distance label from $\Queue$, and if the vertex corresponding to that label is being visited for the first time, we assign it's layer number and activate it in all the Monge groups it belongs to as shown in line \ref{DDG}. For every boundary vertex $u$ activated, we also check if there are any edges $(u,v)$ where $v \in \HSet{A}{F}$. $\textit{LastLayer}$ is used to keep track of the layer where a vertex $\in \HSet{A}{F}$ is discovered for the first time as shown in lines \ref{free} and \ref{type3}. $UPDATE()$ operation is used to update the representative of a Monge group in $\Queue$.
\subsection{Analysis of FastBFS}
\paragraph{}
FastBFS has the same complexity as FR-Dijkstra. Analysis of FR-Dijkstra in section \ref{FR} carries over here. Since there are only $O(n/\sqrt{r})$ edges of type $(b_j,\K_j)$ and $(\K_j,a_j)$, the total time taken to process them is $O(n/\sqrt{r})$. Each boundary vertex can be extracted from the local heaps at most $O(\log{r})$ times in each region. Since there are $O(n/\sqrt{r})$ boundary vertices in total, we do $O((n/\sqrt{r})\log{r})$ extractions from all the local heaps put together. Each extraction is followed by updating new minimum label in the local heaps which takes $O(\log{r})$ time. A vertex extracted from $\Queue$ is activated only once per Monge group. Total run time of FastBFS is $O((n/\sqrt{r})\log^{2}{n})$.
\paragraph{}
While assigning the layers during FastBFS, we can also track the parent of each vertex and hence find an augmenting path in $H$. This gives an overall complexity of $\fivefour$. (See Case 2 in section \ref{choice}).
\section{Faster DFS}
\label{FastDFS}
In this section, we present an FR-Dijkstra style algorithm to perform FINDAUGPATH (DFS) faster. We call it the FastDFS. 
\subsection{Algorithm Overview}
\paragraph{}
We saw in section \ref{FINDAUGPATH} that FINDAUGPATH takes $O(n)$ time. FINDAUGPATH performs partial DFS in BFS layered graph constructed from $H$ to find shortest length augmenting paths in $H$. Given a vertex $u$, FINDAUGPATH would explore all outgoing edges of $u$ to find a valid vertex $v$ such that $v$ is an unvisited vertex during partial DFS and $L(v) = L(u) +1$.
\paragraph{}
In order to do FINDAUGPATH efficiently, we make use of bipartite Monge groups defined for FR-Dijkstra and 2-D dynamic range search trees associated with every bipartite group. With these data structures, we are able to do DFS in time $O((n/\sqrt{r})\log^2{r})$ instead of $O(n)$. Given a vertex $u$, the data structures help us to efficiently find a vertex $v$ such that $v$ is a unvisited neighbor of $u$ and $L(v) = L(u) +1$ without having to explore all outgoing edges of $u$.  
\paragraph{}
To find a valid outgoing edge from $u$ in partial DFS, we query the 2-D Range search trees associated with the bipartite group $(X,Y)$ where the vertex $u$ lies in $X$. The query is an interval $I$ which is  the overlap of 2 intervals.
\begin{itemize}
\item The interval defined by first and last neighbors of $u$ in clockwise order in the region containing $(X,Y)$.
\item The interval defined by the first and last vertices of $Y$ in clockwise order in the Monge group $(X,Y)$.
\end{itemize}
The 2-D Range search tree returns a  boundary vertex $v$ which has a layer number $L(u)+1$ and lies in $I$ and also deletes $v$ from $Y$ in the corresponding Monge group. As a pre-processing step before DFS is performed, the intervals for each vertex $u$ is computed in all the Monge groups $(X,Y)$ where $u$ lies in $X$. The intervals construction is detailed in Section \ref{Interval Construction}.  It is possible that a vertex $v$ returned by the dynamic 2-D Range search tree doesn't have an edge from $u$. This can be checked in $O(\log{r})$ time. If $v$ is a neighbor, it is added to the stack only if it is unvisited vertex and the partial DFS proceeds from $v$. If $v$ is not a neighbor of $u$ or if it has already been marked visited in some other Monge group by partial DFS, the Range search trees are queried till an unvisited neighbor $v'$ with $L(v')= L(u)+1$ is found. Any vertex $v$ returned by Range search tree can be removed from the Range search tree irrespective of whether it is a neighbor of $u$ or not. This is justified in Lemma \ref{edgecrossing} where we show that if the vertex $v$ returned by Range search tree is not a neighbor of $u$, it cannot be a neighbor of any vertex in $X$ of the same Monge group. Because of vertex deletions, the 2-D Range trees are dynamic in nature. However, no re-balancing is required after deleting a vertex. If no valid outgoing edge is found from $u$, partial DFS backtracks by popping $u$ from the stack and continues search from the parent of $u$. This condition for backtracking is same as described in \textit{FINDAUGPATH} Procedure (section \ref{FINDAUGPATH}). The edges of type $(b_j,\K_j)$ and $(\K_j,a_j)$ are handled exclusively as there are only $O(n/\sqrt{r})$ in number. The construction of 2-D Range search trees is described in section \ref{Range search tree}.
\subsection{Interval Construction}
\label{Interval Construction}
\paragraph{}
In FastBFS/FR-Dijkstra, for each vertex $x \in X$, the intervals of vertices in $Y$ in the Monge group $(X,Y)$ is updated online as new vertices are activated. For FastDFS, we construct the intervals as pre-processing step just once for each vertex in each Monge group and then use these intervals to do DFS efficiently.
\paragraph{}
For a vertex $u$ in region $\RH{j}$, its neighbors are defined on each hole/face in circular order, with one neighbor list per hole/face. For the sake of simplicity, we consider only one neighbor list $\N{u}{j}$ for each vertex per region. We use Fakcharoenphol and Rao's technique \cite{frao} to handle a constant number of holes. We know that each Monge group $(X,Y)$ maintains a contiguous set of vertices in circular order in both $X$ and $Y$. Given the first ($N_1$) and last vertex ($N_L$) of $\N{u}{j}$ of $u \in X$ in clockwise order, we can find the range of overlapping interval of vertices of $\N{u}{j}$ in $Y$ in $O(\log{|Y|})$ time. Let $|Y|=k$. Each vertex can have at most 2 overlapping intervals of its neighbors in each Monge group as shown in Figure \ref{fig:overlap}. Note that the overlapping cases shown are not exhaustive. Computing the intervals for all the vertices in all the Monge groups takes $O((n/\sqrt{r})\log^{2}{n})$ time.
\begin{figure}[!ht]
\centering
\includegraphics[width=0.8\textwidth]{./images/overlap.png}
\caption{(a) Single overlap, (b) two overlapping intervals, (c) No overlap}
\label{fig:overlap}
\end{figure}
\paragraph{}
We now redefine \textit{Monge Crossing Property} in terms of connectivity instead of the shortest path. Consider a bipartite Monge graph $(X,Y)$ in region $R'_k$ with intervals defined for each vertex $x \in X$. Consider two vertices $x_i$ and $x_j$ with their intervals defined as $I_i$ and $I_j$ respectively. Then the following lemma holds true.
\begin{lemma}
\label{edgecrossing}
If vertex $v \in I_i \cap I_j$ and $v \in \N{x_j}{k}$, then $v \in \N{x_i}{k}$ and vice versa.
\end{lemma}
\begin{figure}[!ht]
\centering
\includegraphics[width=0.6\textwidth]{./images/dfsoverlap.png}
\caption{Monge Crossing Property for Connectivity}
\label{fig:dfsoverlap}
\end{figure}
\begin{proof}
When 2 edges cross in the bipartite Monge graph, their projection share a common vertex as shown in Figure \ref{fig:dfsoverlap} (Common edge in case of a bipartite graph). $x_j$ reaches $v$ through $u$ and $x_i$ also has a path to $u$ implying it also has a path to $v$.
\end{proof}
In other words, given a Monge group $(X,Y)$, we can say that if $v \in Y \cap I_i$, but  $v \not\in \N{x_i}{k}$, then no vertex $\in X$ has an edge to $v$.
\subsection{Range search tree}
\label{Range search tree}
\paragraph{}
Besides the neighborhood interval construction for all vertices in all bipartite Monge groups, we also maintain a \textit{2-D Range Search tree} $(\RST_i)$ for vertices in $Y$ in each Monge group $(X_i,Y_i)$. The 2-D Range tree has vertices of $Y$ stored in the cyclic order in primary data structure and has the vertices sorted according to their layer numbers in the secondary data structure.
\begin{figure}[!ht]
\centering
\includegraphics[width=1.0\textwidth]{./images/rangetree.png}
\caption{2-D Range Search Tree returns a vertex with specific layer number in the given interval}
\label{fig:rangetree}
\end{figure}
\paragraph{}
Each $\RST_i$ has a construction time of $O(|Y|\log^{2}{|Y|})$ with an overall construction time of $O((n/\sqrt{r})\log^{3}{r})$ which is also $O((n/\sqrt{r})\log^{3}{n})$. Total space usage per $RST$ is $O(|Y|\log{|Y|})$ and the total space used for all the RSTs is $O((n/\sqrt{r})\log^{2}{r})$ or $O((n/\sqrt{r})\log^{2}{n})$. Given a vertex $u$ and its interval in the Monge group $(X_i,Y_i)$, the $\RST_i$ returns a vertex $v$ such that $L(v) = L(u)+1$ in $O(\log^{2}{|Y_i|})$ time. Deleting a vertex from RST has the same complexity as query time i.e. $O(\log^{2}{|Y_i|})$. With Fractional cascading, we can improve the construction time per $\RST_i$ to $O(|Y_i|\log{|Y_i|})$ with query time of $O(\log{|Y_i|})$. Overall construction time of all RSTs can be improved to $O((n/\sqrt{r})\log^{2}{n})$.
\subsection{Algorithm Implementation}
FastDFS uses a stack in place of a queue which was used in BFS. For boundary to boundary edges, we use the Monge groups and their range search tree to find the next candidate in DFS search as shown in line \ref{case3}. Given vertex $u$, the $\RST_i$ returns vertex $v$ s.t. $L(v) = L(u) +1$ and $v$ lies in the range of overlap of intervals defined by \{first and the last element of $N(u)$\} in the region and \{the first and last element of $Y_i$\}. It is possible that $v$ may not have an edge from $u$. This can be checked in $O(\log{n})$ time by doing a binary search for $v$ in the Neighbor list of $u$ which has vertices stored in cyclic order. Search is done in the region that the bipartite Monge group is a part of. Line \ref{samemonge} shows that $v$ is inserted into the stack only after checking its connectivity from $u$ in the current Monge group and if it has not already been visited elsewhere. If there is no connectivity from $u$ to $v$, we can also infer that there can be no connectivity to $v$ from any vertex in $X_i$ corresponding to the current Monge group. Therefore, the vertex $v$ can be removed from the Range search tree. By removing a vertex returned by Range search tree, we ensure that the vertex is never returned again in that Monge group. $\mathcal{V'}$ is the set of all boundary vertices in BFS layered graph reachable from some free vertex of type $B$ in $H$. Just like in BFS, the $(\K_j,a_j)$ edges (see line \ref{case1}) are handled exclusively. A list of edges of type $(\K_j,a_j)$ are maintained for each boundary vertex and updated after every augmentation. This can be done during construction of edges of the region in $H$. The conditions for backtrack are the same as described in section \ref{FINDAUGPATH} (\textit{FINDAUGPATH Procedure}).

\begin{algorithm}[H]
\caption{DFS in FR-Dijkstra Style}\label{alg:DFS}
\begin{algorithmic}[1]
\Procedure{FastDFS}{$H$}
\State $S(visited) = \emptyset$
%\While{$S \neq \mathcal{V}\backslash \bigcup_j (b_j \cup a_j)$}
\While{$S \cap \HSet{B}{F} \neq \HSet{B}{F}$}
\If{Stack.EMPTY()}\label{jumplocation}
\State Stack.PUSH(a free vertex $b$ from $\HSet{B}{F}\backslash S$)
\If{$b \in \bigcup_j \K_j \cup B_F$}
\State $S = S \cup \{b\}$
\Else 
\While{$\exists$ an edge $(b,v)$ of type $(b_j,\K_j)$}
\If{$v \notin S$}
\State Stack.PUSH($v$)
\State $S = S \cup \{v\}$
\State jump to line \ref{stacktop}
\EndIf
\EndWhile
\EndIf
\EndIf
\State $ u \gets$ Stack.TOP()\label{stacktop}
\If{$\exists$ edge $(u,v)$ of type $(\K_j,a_j)$}\label{case1}
%\If{$L(v) == L(u)+1$}
\State Stack.PUSH($v$)
\State Jump to line \ref{jumppoint}
%\EndIf
\EndIf
\For{each $(X_i,Y_i)$ s.t $u \in X_i$}\label{case3}
\If{$\RST_i.QUERY(u)$ returns a vertex $v$ and $v \in N(u)\backslash S$}\label{samemonge}
\State Stack.PUSH($v$)
\State $S = S \cup \{v\}$
\State Remove the vertex $v$ from $\RST_i$
\State Jump to line \ref{jumppoint}
\Else \If{$\RST_i.QUERY(u)$ returns a vertex $v$ and ($v \in S$ or $v \not\in N(u)$)}
\State Remove the vertex $v$ from $\RST_i$
\State Jump to line \ref{samemonge}
\EndIf
\EndIf
\EndFor
\If{Stack.TOP() $\in \HSet{A}{F}$}\Comment{Augmenting path found}\label{jumppoint}
\State Pop All elements of stack and perform augmentation.
\Else
\If{(Stack.TOP() == u) or (L(Stack.TOP()) == LastLayer)}
\If{$u$ is of type $b_j$}
\State $S = S \cup \{u\}$
\EndIf
\State Stack.POP() \Comment{Backtrack}
\EndIf
\EndIf
\EndWhile
\State \textbf{return}
\EndProcedure
\end{algorithmic}
\end{algorithm}
\subsection{Analysis of FastDFS}. 
Each query to $\RST_i$ takes $O(\log{|Y_i|})$ time. Each vertex is in at most $O(\log{|Y_i|})$ Monge groups per region and on average, in $O(\log{r})$ Monge groups in entire graph $H$. For querying all the Monge groups $(X_i,Y_i)$ which have a vertex $u$ in $X_i$ takes amortized time $O(\log^{2}{n})$. However, by removing vertex $x$ from $X$ when there is no valid $y \in Y$ as the next candidate for DFS search, we can ensure that $O(\log^{2}{n})$ query time can be reduced to $O(\log{n})$. Exploring all the $(\K_j,a_j)$ edges takes $O(n/\sqrt{r})$ time. Overall, FastDFS runs in $O((n/\sqrt{r})\log^{2}{n})$. 
\paragraph{}
Combining FastBFS and FastDFS, we get a total run time of BFS+DFS to be $O(n^{6/5}\log^{2}{n})$. Total time taken for augmentation and re-computation of edges in $H$ takes  $O(n^{6/5}\log^{4}{n})$ time. The overall complexity of our maximum cardinality matching for planar bipartite graph algorithm is  $O(n^{6/5}\log^{4}{n})$. The power on log term can be reduced from 4 to 2 using faster connectivity oracles like \cite{klein2005} or \cite{thorup}. Thus the complexity of our algorithm becomes $O(n^{6/5}\log^{2}{n})$.

\section{Alternate BFS}
\paragraph{}
In this section, we show that BFS can be done in a similar fashion as FastDFS using the intervals (section \ref{Interval Construction}) and Range search trees (section \ref{Range search tree}). Unlike FastDFS, we need only 1-D Range search tree ($\RST^*$) for each bipartite Monge group to do FastBFS. We don't need a secondary tree which sorts vertices by layer numbers. Given vertex $u$, the $\RST^*_i$ returns vertex $v$ s.t. $v$ lies in the range of overlap of intervals defined by first and the last element of $N(u)$ in the region and the first and last element of $Y_i$.
\paragraph{}
Pseudo code for Alternate BFS is shown in Algorithm $4$. Lines \ref{Initial11} and \ref{Initial22} handle the initialization of layer numbers to free vertices $\in \HSet{B}{F}$. Exhaustive BFS is done from a vertex $u$ in all Monge groups $(X,Y)$ where $u \in X$ as shown in line \ref{case333}. Vertex $v$ is added to the queue $\Queue$ only if it belongs to $\N{u}{j}$ and the vertex $v$ is removed from the Range search trees of all the Monge groups $(X,Y)$ where $v \in Y$. If $v \not\in \N{u}{j}$, remove $v$ from just the range search tree of the current Monge group. Edges of type $(\K_j,a_j)$ are handled exclusively in line \ref{case111}. FastBFS terminates when the queue $\Queue$ becomes empty.
\paragraph{}
Overall run-time of this FastBFS is same as FastDFS which is $O(n/\sqrt{r}\log^2{n})$.



\begin{algorithm}[H]
\caption{Alternate BFS}\label{alg:BFS2}
\begin{algorithmic}[1]
\Procedure{FastDFS}{$H$}
\State $\forall$ $v \in H$, $\layer{v}= \infty$, $LastLayer= -1$, $S(visited) = \emptyset$
\For{ $v \in \bigcup_j \K_j \cap B_F$}\Comment{Free boundary vertices of type B}\label{Initial11}
\State $\layer{v}=0$
\State $\Queue.PUSH(v)$
\State $S = S \cup \{v\}$
\For{each $(X_i,Y_i) \in H$  s.t. $v \in Y_i$}
\State $RST^*_i.REMOVE(v)$
\EndFor
\EndFor
\For{ $v \in \bigcup_j b_j$}\Comment{Free internal vertices of type B}\label{Initial22}
\State $\layer{v}=0$
\For{ $u \in \N{v}{j}$ }
\If {$u \not\in S$}
\State $\layer{u}=1$
\State $\Queue.PUSH(u)$
\State $S = S \cup \{u\}$
\For{each $(X_i,Y_i) \in H$  s.t. $u \in Y_i$}
\State $RST^*_i.REMOVE(u)$
\EndFor
\EndIf
\EndFor
\EndFor
\While{$!\Queue$.EMPTY()}
%\State $ w \gets$ $\Queue$.Tail()\label{queuetail}
\State $ u \gets$ $\Queue$.Top()\label{queuetop}
\If {$L(u)== LastLayer$}
\State {$\Queue.POP()$}
\State {$\textbf{continue}$}
\EndIf
\While{$\exists$ an edge $(u,v)$ of type $(\K_j,a_j)$}\label{case111}
\If{$v \not\in S$}
\State $L(v) = L(u) + 1$
\State $LastLayer = L(v)$
\State $S = S \cup \{v\}$
\EndIf
\EndWhile
\For{each $(X_i,Y_i)$ s.t $u \in X_i$}\label{case333}
\If{$RST^*_i.QUERY(u)$ returns a vertex $v$ and $v \in N(u)$}\label{samemonge445}
\State $L(v) = L(u) +1$
\If {$v \in \HSet{A}{F}$}
\State $LastLayer = L(v)$
\EndIf
\State $\Queue$.PUSH($v$)
\State $S = S \cup \{v\}$
\For{each $(X_j,Y_j) \in H$  s.t. $v \in Y_j$}
\State $RST^*_j.REMOVE(v)$
\EndFor
\State Jump to line \ref{samemonge445}
\Else \If{$RST^*_i.QUERY(u)$ returns a vertex $v$ and ($v \not\in N(u)$)}
\State $RST^*_i.REMOVE(v)$
\State Jump to line \ref{samemonge445}
\EndIf
\EndIf
\EndFor
\State $\Queue.POP()$
\EndWhile
\State \textbf{return}
\EndProcedure
\end{algorithmic}
\end{algorithm}