= Crossing lemma for multigraphs
{title2=$e\geq4\mu v\Longrightarrow\operatorname{cr}(G)\geq e^3/(64\mu v^2)$}
Here a loopless <multigraph> has $v$ <vertices>, $e$ <edges>, and at most $\mu$ parallel <edges> per pair. In a minimum-crossing drawing, crossings between incident <edges> can be removed by exchanging their initial segments, so every crossing involves four distinct <vertices>. For each parallel class choose an <edge> with probability $1/\mu$ per <edge>, with the remaining probability choosing none. Retain <vertices> independently with probability $p$. The sampled <simple graph> has expected <edge> count $p^2e/\mu$, expected <vertex> count $pv$, and expected crossing count $p^4\operatorname{cr}(G)/\mu^2$. Deleting one <edge> per crossing and using the <planar graph edge bound> gives $p^4\operatorname{cr}(G)/\mu^2\geq p^2e/\mu-3pv$. Choose $p=4\mu v/e$.
Back to article page
