Crossing minimization in perturbed drawings

Due to data compression or low resolution, nearby vertices and edges of a graph drawn in the plane may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map $$\varphi :G\rightarrow {\mathbb {R}}^2$$ φ : G → R 2 . We wish to perturb $$\varphi $$ φ by an arbitrarily small $$\varepsilon >0$$ ε > 0 into a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An $$\varepsilon $$ ε -perturbation, for every $$\varepsilon >0$$ ε > 0 , is given by a piecewise linear map $$\psi _\varepsilon :G\rightarrow {\mathbb {R}}^2$$ ψ ε : G → R 2 with $$\Vert \varphi -\psi _\varepsilon \Vert