The linear edge bound conjecture for k-quasiplanar graphs
The linear edge bound conjecture for k-quasiplanar graphs
A -quasiplanar graph is a graph that can be drawn in the plane with no pairwise crossing edges. The linear edge bound conjecture. For any , a -quasiplanar graph on vertices can have at most
edges for some constant . 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
Sign in to submit a solution.
No solutions have been posted yet.