Crossings between non-homotopic edges

DOI10.1007/978-3-030-68766-3_28arXiv2006.14908MaRDI QIDQ6343804

Gábor Tardos, Géza Tóth, János Pach

Publication date: 26 June 2020

Abstract: We call a multigraph {em 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 $cfrac{m}^{2}n$ 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$ tends to infinity.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

This page was built for publication: Crossings between non-homotopic edges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6343804)