BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

The Crossing Lemma for Multigraphs Toth, Geza

Description

The crossing number $cr(G)$ of a graph $G$ is the minimum number of crossings over all possible drawings of $G$ on the plane. According to the Crossing Lemma, for any simple graph $G$ with $n$ vertices and $e\ge 4n$ edges, $cr(G)\ge {1\over 64}{e^3\over n^2}$. Clearly, this result does not hold for multigraphs (graphs with parallel edges or loops). We find natural conditions that imply the analogue of the Crossing Lemma for multigraphs.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International