Crossings Between Non-homotopic Edges

renyi-admin — Wed, 09 Jun 2021 12:52:18 +0000

Crossings Between Non-homotopic Edges renyi-admin Wed, 06/09/2021 - 14:52

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\) tends to infinity.

Authors

János Pach (Rényi Institute, Budapest)

Gábor Tardos (Rényi Institute, Budapest)

Géza Tóth (Rényi Institute, Budapest)

Link to file

https://arxiv.org/pdf/2006.14908v3.pdf

Link to website

http://arxiv.org/abs/2006.14908v3

tag1

Crossings Between Non-homotopic Edges