Thomas Thierauf, Fabian Wagner

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC^1.

In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to ... more >>>

A. Pavan, Raghunath Tewari, N. V. Vinodchandran

We report progress on the \NL\ vs \UL\ problem.

\begin{itemize}

\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.

\item[-] We investigate the complexity of min-uniqueness - a central

notion in studying the \NL\ vs \UL\ problem.

more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari

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

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>