  In this paper, we give improved bounds for the computational complexity of
computing with planar algebraic curves. More specifically, for arbitrary
coprime polynomials $f$, $g \in \mathbb{Z}[x,y]$ and an arbitrary polynomial $h
\in \mathbb{Z}[x,y]$, each of total degree less than $n$ and with integer
coefficients of absolute value less than $2^\tau$, we show that each of the
following problems can be solved in a deterministic way with a number of bit
operations bounded by $\tilde{O}(n^6+n^5\tau)$, where we ignore polylogarithmic
factors in $n$ and $\tau$:
  (1) The computation of isolating regions in $\mathbb{C}^2$ for all complex
solutions of the system $f = g = 0$,
  (2) the computation of a separating form for the solutions of $f = g = 0$,
  (3) the computation of the sign of $h$ at all real valued solutions of $f = g
= 0$, and
  (4) the computation of the topology of the planar algebraic curve
$\mathcal{C}$ defined as the real valued vanishing set of the polynomial $f$.
  Our bound improves upon the best currently known bounds for the first three
problems by a factor of $n^2$ or more and closes the gap to the
state-of-the-art randomized complexity for the last problem.
