---
_id: '9299'
abstract:
- lang: eng
  text: We call a multigraph non-homotopic if it can be drawn in the plane in such
    a way that no two edges connecting the same pair of vertices can be continuously
    transformed into each other without passing through a vertex, and no loop can
    be shrunk to its end-vertex in the same way. It is easy to see that a non-homotopic
    multigraph on   n>1  vertices can have arbitrarily many edges. We prove that the
    number of crossings between the edges of a non-homotopic multigraph with n vertices
    and   m>4n  edges is larger than   cm2n  for some constant   c>0 , and that this
    bound is tight up to a polylogarithmic factor. We also show that the lower bound
    is not asymptotically sharp as n is fixed and   m⟶∞ .
acknowledgement: Supported by the National Research, Development and Innovation Office,
  NKFIH, KKP-133864, K-131529, K-116769, K-132696, by the Higher Educational Institutional
  Excellence Program 2019 NKFIH-1158-6/2019, the Austrian Science Fund (FWF), grant
  Z 342-N31, by the Ministry of Education and Science of the Russian Federation MegaGrant
  No. 075-15-2019-1926, and by the ERC Synergy Grant “Dynasnet” No. 810115. A full
  version can be found at https://arxiv.org/abs/2006.14908.
article_processing_charge: No
arxiv: 1
author:
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
- first_name: Gábor
  full_name: Tardos, Gábor
  last_name: Tardos
- first_name: Géza
  full_name: Tóth, Géza
  last_name: Tóth
citation:
  ama: 'Pach J, Tardos G, Tóth G. Crossings between non-homotopic edges. In: <i>28th
    International Symposium on Graph Drawing and Network Visualization</i>. Vol 12590.
    LNCS. Springer Nature; 2020:359-371. doi:<a href="https://doi.org/10.1007/978-3-030-68766-3_28">10.1007/978-3-030-68766-3_28</a>'
  apa: 'Pach, J., Tardos, G., &#38; Tóth, G. (2020). Crossings between non-homotopic
    edges. In <i>28th International Symposium on Graph Drawing and Network Visualization</i>
    (Vol. 12590, pp. 359–371). Virtual, Online: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-68766-3_28">https://doi.org/10.1007/978-3-030-68766-3_28</a>'
  chicago: Pach, János, Gábor Tardos, and Géza Tóth. “Crossings between Non-Homotopic
    Edges.” In <i>28th International Symposium on Graph Drawing and Network Visualization</i>,
    12590:359–71. LNCS. Springer Nature, 2020. <a href="https://doi.org/10.1007/978-3-030-68766-3_28">https://doi.org/10.1007/978-3-030-68766-3_28</a>.
  ieee: J. Pach, G. Tardos, and G. Tóth, “Crossings between non-homotopic edges,”
    in <i>28th International Symposium on Graph Drawing and Network Visualization</i>,
    Virtual, Online, 2020, vol. 12590, pp. 359–371.
  ista: 'Pach J, Tardos G, Tóth G. 2020. Crossings between non-homotopic edges. 28th
    International Symposium on Graph Drawing and Network Visualization. GD: Graph
    Drawing and Network VisualizationLNCS vol. 12590, 359–371.'
  mla: Pach, János, et al. “Crossings between Non-Homotopic Edges.” <i>28th International
    Symposium on Graph Drawing and Network Visualization</i>, vol. 12590, Springer
    Nature, 2020, pp. 359–71, doi:<a href="https://doi.org/10.1007/978-3-030-68766-3_28">10.1007/978-3-030-68766-3_28</a>.
  short: J. Pach, G. Tardos, G. Tóth, in:, 28th International Symposium on Graph Drawing
    and Network Visualization, Springer Nature, 2020, pp. 359–371.
conference:
  end_date: 2020-09-18
  location: Virtual, Online
  name: 'GD: Graph Drawing and Network Visualization'
  start_date: 2020-09-16
date_created: 2021-03-28T22:01:44Z
date_published: 2020-09-20T00:00:00Z
date_updated: 2021-04-06T11:32:32Z
day: '20'
department:
- _id: HeEd
doi: 10.1007/978-3-030-68766-3_28
external_id:
  arxiv:
  - '2006.14908'
intvolume: '     12590'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2006.14908
month: '09'
oa: 1
oa_version: Preprint
page: 359-371
project:
- _id: 268116B8-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z00342
  name: The Wittgenstein Prize
publication: 28th International Symposium on Graph Drawing and Network Visualization
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783030687656'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Crossings between non-homotopic edges
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12590
year: '2020'
...