On the number of edges of separated multigraphs

Fox, Jacob and Pach, János and Suk, Andrew (2023) On the number of edges of separated multigraphs. JOURNAL OF GRAPH THEORY. ISSN 0364-9024

Preview

Text 2108.11290.pdf Download (130kB) | Preview

Abstract

We prove that the number of edges of a multigraph G $G$ with n $n$ vertices is at most O(n2log n) $O({n}<^>{2}\mathrm{log}\unicode{x0200A}n)$, provided that any two edges cross at most once, parallel edges are noncrossing, and the lens enclosed by every pair of parallel edges in G $G$ contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi, and Leighton, if G $G$ has e & GE;4n $e\ge 4n$ edges, in any drawing of G $G$ with the above property, the number of crossings is & omega;e3n2log(e/n) ${\rm{\Omega }}\left(\frac{{e}<^>{3}}{{n}<^>{2}\mathrm{log}(e\unicode{x02215}n)}\right)$. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.

Actions (login required)

Edit Item