---
res:
bibo_abstract:
- 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⟶∞ .@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: János
foaf_name: Pach, János
foaf_surname: Pach
foaf_workInfoHomepage: http://www.librecat.org/personId=E62E3130-B088-11EA-B919-BF823C25FEA4
- foaf_Person:
foaf_givenName: Gábor
foaf_name: Tardos, Gábor
foaf_surname: Tardos
- foaf_Person:
foaf_givenName: Géza
foaf_name: Tóth, Géza
foaf_surname: Tóth
bibo_doi: 10.1007/978-3-030-68766-3_28
bibo_volume: 12590
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
- http://id.crossref.org/issn/1611-3349
- http://id.crossref.org/issn/9783030687656
dct_language: eng
dct_publisher: Springer Nature@
dct_title: Crossings between non-homotopic edges@
...