  Let $G$ be a connected planar (but not yet embedded) graph and $F$ a set of
additional edges not yet in $G$. The {multiple edge insertion} problem (MEI)
asks for a drawing of $G+F$ with the minimum number of pairwise edge crossings,
such that the subdrawing of $G$ is plane. An optimal solution to this problem
approximates the crossing number of the graph $G+F$.
  Finding an exact solution to MEI is NP-hard for general $F$, but linear time
solvable for the special case of $|F|=1$ (SODA01, Algorithmica) or when all of
$F$ are incident to a new vertex (SODA09).
  The complexity for general $F$ but with constant $k=|F|$ was open, but
algorithms both with relative and absolute approximation guarantees have been
presented (SODA11, ICALP11). We show that the problem is fixed parameter
tractable (FPT) in $k$ for biconnected $G$, or if the cut vertices of $G$ have
degrees bounded by a constant. We give the first exact algorithm for this
problem; it requires only $O(|V(G)|)$ time for any constant $k$.
