  We present a deterministic fully-dynamic data structure for maintaining
information about the bridges in a graph. We support updates in
$\tilde{O}((\log n)^2)$ amortized time, and can find a bridge in the component
of any given vertex, or a bridge separating any two given vertices, in $O(\log
n / \log \log n)$ worst case time. Our bounds match the current best for bounds
for deterministic fully-dynamic connectivity up to $\log\log n$ factors. The
previous best dynamic bridge finding was an $\tilde{O}((\log n)^3)$ amortized
time algorithm by Thorup [STOC2000], which was a bittrick-based improvement on
the $O((\log n)^4)$ amortized time algorithm by Holm et al.[STOC98, JACM2001].
  Our approach is based on a different and purely combinatorial improvement of
the algorithm of Holm et al., which by itself gives a new combinatorial
$\tilde{O}((\log n)^3)$ amortized time algorithm. Combining it with Thorup's
bittrick, we get down to the claimed $\tilde{O}((\log n)^2)$ amortized time.
  Essentially the same new trick can be applied to the biconnectivity data
structure from [STOC98, JACM2001], improving the amortized update time to
$\tilde{O}((\log n)^3)$.
  We also offer improvements in space. We describe a general trick which
applies to both of our new algorithms, and to the old ones, to get down to
linear space, where the previous best use $O(m + n\log n\log\log n)$. Finally,
we show how to obtain $O(\log n/\log \log n)$ query time, matching the optimal
trade-off between update and query time.
  Our result yields an improved running time for deciding whether a unique
perfect matching exists in a static graph.
