The Constrained Crossing Minimization Problem - A First Approach

defined as follows. Given a connected, planar graph $G=(V,E)$, a combinatorial
embedding $\Pi(G)$ of $G$, and a set of pairwise distinct edges
$F\subseteq V\times V$, find a
drawing of $G'=(V,E\cup F)$ in the plane such that the combinatorial embedding
$\Pi(G)$ of $G$ is preserved and the number of edge crossings is minimum.
This problem arises in the context of automatic graph drawing.