---
_id: '11185'
abstract:
- lang: eng
  text: Bundling crossings is a strategy which can enhance the readability of graph
    drawings. In this paper we consider bundlings for families of pseudosegments,
    i.e., simple curves such that any two have share at most one point at which they
    cross. Our main result is that there is a polynomial-time algorithm to compute
    an 8-approximation of the bundled crossing number of such instances (up to adding
    a term depending on the facial structure). This 8-approximation also holds for
    bundlings of good drawings of graphs. In the special case of circular drawings
    the approximation factor is 8 (no extra term), this improves upon the 10-approximation
    of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection
    graph of the pseudosegments is bipartite.
acknowledgement: This work was initiated during the Workshop on Geometric Graphs in
  November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian
  Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during
  the workshop. The first author has received funding from the European Union’s Horizon
  2020 research and innovation programme under the Marie Sklodowska Curie grant agreement
  No 754411. The second author has been supported by the German Research Foundation
  DFG Project FE 340/12-1.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alan M
  full_name: Arroyo Guevara, Alan M
  id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
  last_name: Arroyo Guevara
  orcid: 0000-0003-2401-8670
- first_name: Stefan
  full_name: Felsner, Stefan
  last_name: Felsner
citation:
  ama: 'Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. In:
    <i>WALCOM 2022: Algorithms and Computation</i>. Vol 13174. LNCS. Springer Nature;
    2022:383-395. doi:<a href="https://doi.org/10.1007/978-3-030-96731-4_31">10.1007/978-3-030-96731-4_31</a>'
  apa: 'Arroyo Guevara, A. M., &#38; Felsner, S. (2022). Approximating the bundled
    crossing number. In <i>WALCOM 2022: Algorithms and Computation</i> (Vol. 13174,
    pp. 383–395). Jember, Indonesia: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-96731-4_31">https://doi.org/10.1007/978-3-030-96731-4_31</a>'
  chicago: 'Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled
    Crossing Number.” In <i>WALCOM 2022: Algorithms and Computation</i>, 13174:383–95.
    LNCS. Springer Nature, 2022. <a href="https://doi.org/10.1007/978-3-030-96731-4_31">https://doi.org/10.1007/978-3-030-96731-4_31</a>.'
  ieee: 'A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing
    number,” in <i>WALCOM 2022: Algorithms and Computation</i>, Jember, Indonesia,
    2022, vol. 13174, pp. 383–395.'
  ista: 'Arroyo Guevara AM, Felsner S. 2022. Approximating the bundled crossing number.
    WALCOM 2022: Algorithms and Computation. WALCOM: Algorithms and ComputationLNCS
    vol. 13174, 383–395.'
  mla: 'Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing
    Number.” <i>WALCOM 2022: Algorithms and Computation</i>, vol. 13174, Springer
    Nature, 2022, pp. 383–95, doi:<a href="https://doi.org/10.1007/978-3-030-96731-4_31">10.1007/978-3-030-96731-4_31</a>.'
  short: 'A.M. Arroyo Guevara, S. Felsner, in:, WALCOM 2022: Algorithms and Computation,
    Springer Nature, 2022, pp. 383–395.'
conference:
  end_date: 2022-03-26
  location: Jember, Indonesia
  name: 'WALCOM: Algorithms and Computation'
  start_date: 2022-03-24
date_created: 2022-04-17T22:01:47Z
date_published: 2022-03-16T00:00:00Z
date_updated: 2023-09-25T10:56:10Z
day: '16'
department:
- _id: UlWa
doi: 10.1007/978-3-030-96731-4_31
ec_funded: 1
external_id:
  arxiv:
  - '2109.14892'
intvolume: '     13174'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2109.14892'
month: '03'
oa: 1
oa_version: Preprint
page: 383-395
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 'WALCOM 2022: Algorithms and Computation'
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783030967307'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '13969'
    relation: later_version
    status: public
scopus_import: '1'
series_title: LNCS
status: public
title: Approximating the bundled crossing number
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13174
year: '2022'
...