---
_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'
...