The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in ... more >>>

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 ... more >>>

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.
The obvious way to construct such a reduction is via a {\em planarizing ... more >>>

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\Omega(n/\log n)$ in the Polynomial ... more >>>