@inproceedings{5791,
  abstract     = {Due to data compression or low resolution, nearby vertices and edges of a graph drawing may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map φ:G → ℝ. We wish to perturb φ by an arbitrarily small ε>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 ε-perturbation, for every ε>0, is given by a piecewise linear map (Formula Presented), where with ||·|| is the uniform norm (i.e., sup norm). We present a polynomial-time solution for this optimization problem when G is a cycle and the map φ has no spurs (i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) when G is an arbitrary graph and φ has no spurs, and (ii) when φ may have spurs and G is a cycle or a union of disjoint paths.},
  author       = {Fulek, Radoslav and Tóth, Csaba D.},
  isbn         = {9783030044138},
  location     = {Barcelona, Spain},
  pages        = {229--241},
  publisher    = {Springer},
  title        = {{Crossing minimization in perturbed drawings}},
  doi          = {10.1007/978-3-030-04414-5_16},
  volume       = {11282 },
  year         = {2018},
}