On the number of edges of separated multigraphs

DOI10.1007/978-3-030-92931-2_16arXiv2108.11290MaRDI QIDQ6375998

János Pach, Andrew Suk, Jacob Fox

Publication date: 25 August 2021

Abstract: We prove that the number of edges of a multigraph $G$ with $n$ vertices is at most $O(n^{2}logn)$, 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$ contains at least one vertex. As a consequence, we prove the following extension of the Crossing Lemma of Ajtai, Chv'atal, Newborn, Szemer'edi and Leighton, if $G$ has $egeq4n$ edges, in any drawing of $G$ with the above property, the number of crossings is $Omegaleft(frac{e}^3{n}^{2}log(e/n)ight)$. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.

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: On the number of edges of separated multigraphs

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