---
_id: '13969'
abstract:
- lang: eng
  text: "Bundling crossings is a strategy which can enhance the readability\r\nof
    graph drawings. In this paper we consider good drawings, i.e., we require that\r\nany
    two edges have at most one common point which can be a common vertex or a\r\ncrossing.
    Our main result is that there is a polynomial-time algorithm to compute an\r\n8-approximation
    of the bundled crossing number of a good drawing with no toothed\r\nhole. In general
    the number of toothed holes has to be added to the 8-approximation.\r\nIn the
    special case of circular drawings the approximation factor is 8, this improves\r\nupon
    the 10-approximation of Fink et al. [14]. Our approach also works with the same\r\napproximation
    factor for families of pseudosegments, i.e., curves intersecting at most\r\nonce.
    We also show how to compute a 9/2-approximation when the intersection graph of\r\nthe
    pseudosegments is bipartite and has no toothed hole."
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 Sk lodowska-Curie grant agreement
  No 754411. The second author has been supported by the German Research Foundation
  DFG Project FE 340/12-1. An extended abstract of this paper has been published in
  the proceedings of WALCOM 2022 in the Springer LNCS series, vol. 13174, pages 383–395.
article_processing_charge: Yes
article_type: original
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. <i>Journal
    of Graph Algorithms and Applications</i>. 2023;27(6):433-457. doi:<a href="https://doi.org/10.7155/jgaa.00629">10.7155/jgaa.00629</a>
  apa: Arroyo Guevara, A. M., &#38; Felsner, S. (2023). Approximating the bundled
    crossing number. <i>Journal of Graph Algorithms and Applications</i>. Brown University.
    <a href="https://doi.org/10.7155/jgaa.00629">https://doi.org/10.7155/jgaa.00629</a>
  chicago: Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled
    Crossing Number.” <i>Journal of Graph Algorithms and Applications</i>. Brown University,
    2023. <a href="https://doi.org/10.7155/jgaa.00629">https://doi.org/10.7155/jgaa.00629</a>.
  ieee: A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,”
    <i>Journal of Graph Algorithms and Applications</i>, vol. 27, no. 6. Brown University,
    pp. 433–457, 2023.
  ista: Arroyo Guevara AM, Felsner S. 2023. Approximating the bundled crossing number.
    Journal of Graph Algorithms and Applications. 27(6), 433–457.
  mla: Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing
    Number.” <i>Journal of Graph Algorithms and Applications</i>, vol. 27, no. 6,
    Brown University, 2023, pp. 433–57, doi:<a href="https://doi.org/10.7155/jgaa.00629">10.7155/jgaa.00629</a>.
  short: A.M. Arroyo Guevara, S. Felsner, Journal of Graph Algorithms and Applications
    27 (2023) 433–457.
date_created: 2023-08-06T22:01:11Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-09-25T10:56:10Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.7155/jgaa.00629
ec_funded: 1
external_id:
  arxiv:
  - '2109.14892'
file:
- access_level: open_access
  checksum: 9c30d2b8e324cc1c904f2aeec92013a3
  content_type: application/pdf
  creator: dernst
  date_created: 2023-08-07T08:00:48Z
  date_updated: 2023-08-07T08:00:48Z
  file_id: '13979'
  file_name: 2023_JourGraphAlgorithms_Arroyo.pdf
  file_size: 865774
  relation: main_file
  success: 1
file_date_updated: 2023-08-07T08:00:48Z
has_accepted_license: '1'
intvolume: '        27'
issue: '6'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 433-457
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Journal of Graph Algorithms and Applications
publication_identifier:
  issn:
  - 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
  record:
  - id: '11185'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Approximating the bundled crossing number
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2023'
...
---
_id: '11938'
abstract:
- lang: eng
  text: A matching is compatible to two or more labeled point sets of size n with
    labels {1, . . . , n} if its straight-line drawing on each of these point sets
    is crossing-free. We study the maximum number of edges in a matching compatible
    to two or more labeled point sets in general position in the plane. We show that
    for any two labeled sets of n points in convex position there exists a compatible
    matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets
    we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound,
    we use probabilistic arguments to show that for any ℓ given sets of n points there
    exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1))
    edges. Finally, we show that Θ(log n) copies of any set of n points are necessary
    and sufficient for the existence of labelings of these point sets such that any
    compatible matching consists only of a single edge.
acknowledgement: 'A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411.
  Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
  no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
  DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
  by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
  ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
  (RiSE).'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oswin
  full_name: Aichholzer, Oswin
  last_name: Aichholzer
- 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: Zuzana
  full_name: Masárová, Zuzana
  id: 45CFE238-F248-11E8-B48F-1D18A9856A87
  last_name: Masárová
  orcid: 0000-0002-6660-1322
- first_name: Irene
  full_name: Parada, Irene
  last_name: Parada
- first_name: Daniel
  full_name: Perz, Daniel
  last_name: Perz
- first_name: Alexander
  full_name: Pilz, Alexander
  last_name: Pilz
- first_name: Josef
  full_name: Tkadlec, Josef
  id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
  last_name: Tkadlec
  orcid: 0000-0002-1097-9684
- first_name: Birgit
  full_name: Vogtenhuber, Birgit
  last_name: Vogtenhuber
citation:
  ama: Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
    <i>Journal of Graph Algorithms and Applications</i>. 2022;26(2):225-240. doi:<a
    href="https://doi.org/10.7155/jgaa.00591">10.7155/jgaa.00591</a>
  apa: Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
    Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. <i>Journal of Graph
    Algorithms and Applications</i>. Brown University. <a href="https://doi.org/10.7155/jgaa.00591">https://doi.org/10.7155/jgaa.00591</a>
  chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
    Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
    Matchings.” <i>Journal of Graph Algorithms and Applications</i>. Brown University,
    2022. <a href="https://doi.org/10.7155/jgaa.00591">https://doi.org/10.7155/jgaa.00591</a>.
  ieee: O. Aichholzer <i>et al.</i>, “On compatible matchings,” <i>Journal of Graph
    Algorithms and Applications</i>, vol. 26, no. 2. Brown University, pp. 225–240,
    2022.
  ista: Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
    J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and
    Applications. 26(2), 225–240.
  mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” <i>Journal of Graph Algorithms
    and Applications</i>, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:<a
    href="https://doi.org/10.7155/jgaa.00591">10.7155/jgaa.00591</a>.
  short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
    J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022)
    225–240.
date_created: 2022-08-21T22:01:56Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-02-23T13:54:21Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.7155/jgaa.00591
ec_funded: 1
external_id:
  arxiv:
  - '2101.03928'
file:
- access_level: open_access
  checksum: dc6e255e3558faff924fd9e370886c11
  content_type: application/pdf
  creator: dernst
  date_created: 2022-08-22T06:42:42Z
  date_updated: 2022-08-22T06:42:42Z
  file_id: '11940'
  file_name: 2022_JourGraphAlgorithmsApplic_Aichholzer.pdf
  file_size: 694538
  relation: main_file
  success: 1
file_date_updated: 2022-08-22T06:42:42Z
has_accepted_license: '1'
intvolume: '        26'
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 225-240
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P 23499-N23
  name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
publication: Journal of Graph Algorithms and Applications
publication_identifier:
  issn:
  - 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
  record:
  - id: '9296'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: On compatible matchings
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2022'
...