Crossings between non-homotopic edges

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

Author name not available (Why is that?)

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 > 4 n

edges is larger than

c f r a c 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

No records found.

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)