Graphs drawn with few crossings per edge (Q1272189): Difference between revisions

If a graph with \(v\) vertices and \(e\) edges can be drawn on the plane so that every edge crosses at most \(k\) others, then \(e\leq (k+3)(v-2)4\) for \(k\leq 4\) and \(e\leq 4.108 \sqrt{k}v\) in general. For the crossing number \(c\) (the minimal number of edge crossings over all planar drawings) the estimate \(c> 0.029 e^3/v^2 - 0.9 v \) is proved. This can be used to improve the constants in the Szemerédi-Trotter theorem.