A crossing lemma for multigraphs (Q2189737)

Let \(G\) be a drawing of a graph with \(n\) vertices and \(e > 4n\) edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the crossing lemma of \textit{M. Ajtai} et al. [Ann. Discrete Math. 12, 9--12 (1982; Zbl 0502.05021)] and \textit{F. T. Leighton} [Complexity issues in VLSI. Optimal layouts for the shuffle-exchange graph and other networks. Cambridge: MIT Press (1983)], the number of crossings in \(G\) is at least \(c\frac{e^3}{n^2}\), for a suitable constant \(c > 0\). \textit{L. A. Székely} [Comb. Probab. Comput. 6, No. 3, 353--358 (1997; Zbl 0882.52007)] generalized this result to multigraphs, establishing the lower bound \(c\frac{e^3}{mn^2}\), where \(m\) denotes the maximum multiplicity of an edge in \(G\). In this paper, the authors get rid of the dependence on \(m\) by showing that, as in the original crossing lemma, the number of crossings is at least \(c^\prime\frac{e^3}{n^2}\) for some \(c^\prime> 0\), provided that the ``lens'' (a region bounded by two parallel edges) enclosed by every pair of parallel edges in \(G\) contains at least one vertex. This settles a conjecture of Bekos, Kaufmann, and Raftopoulou.