We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in UL;
2. a Hall Obstacle in bipartite planar graphs is in NL;
3. an Even Perfect Matching in bipartite planar graphs is in NL; and
4. an Even Path in planar DAGs is in UL.
For the proof of 2 and 3, we revisit the flow technique of Miller and Naor [MN89]
which was used to provide an NC algorithm for bipartite planar matching construction.
To obtain the main result (item 1 above), we combine it in a simple but subtle way with
the double counting technique of Reinhardt and Allender [RA00] to yield the UL bound.
To prove the UL bound in 4 above, we combine two existing isolation techniques (viz.
[BTV09] and [FKS84, Hoa10]) in a non-obvious way.

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in UL;
2. a Hall Obstacle in bipartite planar graphs is in NL;
3. an Even Perfect Matching in bipartite planar graphs is in NL; and
4. an Even Path in planar DAGs is in UL.
For the proof of 2 and 3, we revisit the flow technique of Miller and Naor [MN89]
which was used to provide an NC algorithm for bipartite planar matching construction.
To obtain the main result (item 1 above), we combine it in a simple but subtle way with
the double counting technique of Reinhardt and Allender [RA00] to yield the UL bound.
To prove the UL bound in 4 above, we combine two existing isolation techniques (viz.
[BTV09] and [FKS84, Hoa10]) in a non-obvious way.