[{"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⟶∞ ."}],"intvolume":"     12590","department":[{"_id":"HeEd"}],"date_published":"2020-09-20T00:00:00Z","external_id":{"arxiv":["2006.14908"]},"oa":1,"language":[{"iso":"eng"}],"article_processing_charge":"No","main_file_link":[{"url":"https://arxiv.org/abs/2006.14908","open_access":"1"}],"arxiv":1,"series_title":"LNCS","scopus_import":"1","status":"public","publication":"28th International Symposium on Graph Drawing and Network Visualization","project":[{"name":"Mathematics, Computer Science","grant_number":"Z00342","_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"publication_status":"published","conference":{"location":"Virtual, Online","end_date":"2020-09-18","name":"GD: Graph Drawing and Network Visualization","start_date":"2020-09-16"},"citation":{"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>","short":"J. Pach, G. Tardos, G. Tóth, in:, 28th International Symposium on Graph Drawing and Network Visualization, Springer Nature, 2020, 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.","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>","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>.","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>.","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."},"page":"359-371","date_created":"2021-03-28T22:01:44Z","type":"conference","author":[{"last_name":"Pach","id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János","first_name":"János"},{"first_name":"Gábor","full_name":"Tardos, Gábor","last_name":"Tardos"},{"last_name":"Tóth","full_name":"Tóth, Géza","first_name":"Géza"}],"month":"09","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.1007/978-3-030-68766-3_28","_id":"9299","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.","publisher":"Springer Nature","day":"20","year":"2020","title":"Crossings between non-homotopic edges","oa_version":"Preprint","quality_controlled":"1","publication_identifier":{"issn":["0302-9743"],"isbn":["9783030687656"],"eissn":["1611-3349"]},"fulldoi":"https://doi.org/10.1007/978-3-030-68766-3_28","volume":12590,"date_updated":"2025-04-15T07:16:52Z"}]