--- _id: '5791' abstract: - lang: eng text: 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. alternative_title: - LNCS article_processing_charge: No author: - first_name: Radoslav full_name: Fulek, Radoslav id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87 last_name: Fulek orcid: 0000-0001-8485-1774 - first_name: Csaba D. full_name: Tóth, Csaba D. last_name: Tóth citation: ama: 'Fulek R, Tóth CD. Crossing minimization in perturbed drawings. In: Vol 11282. Springer; 2018:229-241. doi:10.1007/978-3-030-04414-5_16' apa: 'Fulek, R., & Tóth, C. D. (2018). Crossing minimization in perturbed drawings (Vol. 11282, pp. 229–241). Presented at the Graph Drawing and Network Visualization, Barcelona, Spain: Springer. https://doi.org/10.1007/978-3-030-04414-5_16' chicago: Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed Drawings,” 11282:229–41. Springer, 2018. https://doi.org/10.1007/978-3-030-04414-5_16. ieee: R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented at the Graph Drawing and Network Visualization, Barcelona, Spain, 2018, vol. 11282, pp. 229–241. ista: Fulek R, Tóth CD. 2018. Crossing minimization in perturbed drawings. Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241. mla: Fulek, Radoslav, and Csaba D. Tóth. Crossing Minimization in Perturbed Drawings. Vol. 11282, Springer, 2018, pp. 229–41, doi:10.1007/978-3-030-04414-5_16. short: R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241. conference: end_date: 2018-09-28 location: Barcelona, Spain name: Graph Drawing and Network Visualization start_date: 2018-09-26 date_created: 2018-12-30T22:59:15Z date_published: 2018-12-18T00:00:00Z date_updated: 2023-09-11T12:49:55Z day: '18' department: - _id: UlWa doi: 10.1007/978-3-030-04414-5_16 external_id: arxiv: - '1808.07608' isi: - '000672802500016' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1808.07608 month: '12' oa: 1 oa_version: Preprint page: 229-241 publication_identifier: isbn: - '9783030044138' publication_status: published publisher: Springer quality_controlled: '1' scopus_import: '1' status: public title: Crossing minimization in perturbed drawings type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: '11282 ' year: '2018' ...