The linear edge bound conjecture for k-quasiplanar graphs

A kk-quasiplanar graph is a graph that can be drawn in the plane with no kk pairwise crossing edges. The linear edge bound conjecture. For any k>1k>1, a kk-quasiplanar graph on nn vertices can have at most

cknc_k n

edges for some constant ck>0c_k>0. This is a long-standing conjecture about the extremal density of quasiplanar graphs; the paper does not state a resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Panna Gehér and Géza Tóth, “1-planar unit distance graphs”, arXiv:2310.00940 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.