---
_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
arxiv: 1
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:<a href="https://doi.org/10.1007/978-3-030-04414-5_16">10.1007/978-3-030-04414-5_16</a>'
  apa: 'Fulek, R., &#38; Tóth, C. D. (2018). Crossing minimization in perturbed drawings
    (Vol. 11282, pp. 229–241). Presented at the GD: Graph Drawing and Network Visualization,
    Barcelona, Spain: Springer. <a href="https://doi.org/10.1007/978-3-030-04414-5_16">https://doi.org/10.1007/978-3-030-04414-5_16</a>'
  chicago: Fulek, Radoslav, and Csaba D. Tóth. “Crossing Minimization in Perturbed
    Drawings,” 11282:229–41. Springer, 2018. <a href="https://doi.org/10.1007/978-3-030-04414-5_16">https://doi.org/10.1007/978-3-030-04414-5_16</a>.
  ieee: 'R. Fulek and C. D. Tóth, “Crossing minimization in perturbed drawings,” presented
    at the GD: 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. GD:
    Graph Drawing and Network Visualization, LNCS, vol. 11282, 229–241.'
  mla: Fulek, Radoslav, and Csaba D. Tóth. <i>Crossing Minimization in Perturbed Drawings</i>.
    Vol. 11282, Springer, 2018, pp. 229–41, doi:<a href="https://doi.org/10.1007/978-3-030-04414-5_16">10.1007/978-3-030-04414-5_16</a>.
  short: R. Fulek, C.D. Tóth, in:, Springer, 2018, pp. 229–241.
conference:
  end_date: 2018-09-28
  location: Barcelona, Spain
  name: 'GD: 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: 2025-07-10T11:53:00Z
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: '11282 '
year: '2018'
...