A successful concept for measuring non-planarity of graphs: the crossing number Original Research Article

This paper surveys how the concept of crossing number, which used to be familiar only to a limited group of specialists, emerges as a significant graph parameter. This paper has dual purposes: first, it reviews foundational, historical, and philosophical issues of crossing numbers, second, it shows a new lower bound for crossing numbers. This new lower bound may be helpful in estimating crossing numbers.