  We give a new upper bound on the quantum query complexity of deciding
$st$-connectivity on certain classes of planar graphs, and show the bound is
sometimes exponentially better than previous results. We then show Boolean
formula evaluation reduces to deciding connectivity on just such a class of
graphs. Applying the algorithm for $st$-connectivity to Boolean formula
evaluation problems, we match the $O(\sqrt{N})$ bound on the quantum query
complexity of evaluating formulas on $N$ variables, give a quadratic speed-up
over the classical query complexity of a certain class of promise Boolean
formulas, and show this approach can yield superpolynomial quantum/classical
separations. These results indicate that this $st$-connectivity-based approach
may be the "right" way of looking at quantum algorithms for formula evaluation.
