The quasi-plane graph linear density conjecture
The quasi-plane graph linear density conjecture
Call a topological graph -quasi-plane if it has no pairwise crossing edges. The quasi-plane graph linear density conjecture. For any integer there is a constant such that every -vertex -quasi-plane graph has at most edges.
This conjecture would imply the linear edge bound for PCC simple topological graphs. It is known for , for , and for convex geometric graphs for every , but remains open for .
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
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.