The quasi-plane graph linear density conjecture

Call a topological graph kk-quasi-plane if it has no kk pairwise crossing edges. The quasi-plane graph linear density conjecture. For any integer k2k \geq 2 there is a constant ckc_k such that every nn-vertex kk-quasi-plane graph has at most cknc_kn edges.

This conjecture would imply the linear edge bound for PCC simple topological graphs. It is known for k=3k=3, for k=4k=4, and for convex geometric graphs for every kk, but remains open for k5k \geq 5.

Sources & referencesView supporting material

Primary source

Eyal Ackerman, Balázs Keszegh and Mate Vizer, “On the size of planarly connected crossing graphs”, arXiv:1509.02475 (2016).

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.