We show that if a graph G with n >= 3 vertices can be drawn in the plane such that each of its edges is involved in at most four crossings, then G has at most 6n - 12 edges. This settles a conjecture of Pach, Radoicic, Tardos, and Toth, and yields a better bound for the famous Crossing Lemma: The crossing number, cr(G), of a (not too sparse) graph G with n vertices and m edges is at least cm(3)/n(2) where c > 1/29. This bound is known to be tight, apart from the constant c for which the previous best lower bound was 1/31.1. (C) 2019 Elsevier B.V. All rights reserved.
展开▼
