On the number of edges of separated multigraphs

We prove that the number of edges of a multigraph G with n vertices is at most O(n(2)log 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 >= 4n edges, in any drawing of G with the above property, the number of crossings is O( e) n log(e n)3 2 /. This answers a question of Kaufmann et al. and is tight up to the logarithmic factor.