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 on the complexity of several other computational problems on planar graphs. All of these problems are shown to be solvable in logarithmic time on a concurrent-read exclusive-write (CREW) PRAM. The new upper bounds are provided by making use of a known characterization of CREW algorithms in terms of "unambiguous" AC$^1$ circuits. This seems to be the first occasion where this characterization has been used in order to provide new upper bounds on natural problems.
The proof of Theorem 2 has a serious flaw that we are unable to resolve. In particular, the statement that our inductive definition translates directly into unambiguous gates is incorrect. A revision will be posted at a later date.
