Details

Autor(en) / Beteiligte

• Ackerman, Eyal

Titel

On topological graphs with at most four crossings per edge

Ist Teil von

• Computational geometry : theory and applications, 2019-12, Vol.85, p.101574, Article 101574

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2019

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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, Radoičić, Tardos, and Tóth, 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 cm3n2, 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.