We prove that the number of edges of a multigraph $G$ with $n$ vertices is at most $O(n^2log 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$ 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$ has $e geq 4n$ edges, in any drawing of $G$ with the above property, the number of crossings is $Omegaleft(frac{e^3}{n^2log(e/n)}right)$. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.
تحميل البحث