Disjoint crossing families conjecture for geometric graphs

From papers

A geometric graph is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. For integers k,l1k,l\geq 1, a (k,l)(k,l)-crossing family is a pair of edge subsets E1,E2E_1,E_2 such that E1=k|E_1|=k, E2=l|E_2|=l, the edges in each subset are pairwise crossing, and every edge in E1E_1 is disjoint from every edge in E2E_2. Disjoint crossing families conjecture. Given fixed constants k,l1k,l\geq 1, there exists a constant ck,lc_{k,l} such that any geometric graph on nn vertices with no (k,l)(k,l)-crossing family has at most ck,lnc_{k,l}n edges. The conjecture is an extremal question about forbidden crossing and disjointness patterns in geometric graphs. The case (k,l)=(2,1)(k,l)=(2,1) is proved with an O(n)O(n) bound, while the general case remains open; the analogous assertion for topological graphs is false.

Progress summary

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

Sources & referencesView supporting material

Primary source

Radoslav Fulek and Andrew Suk, “On disjoint crossing families in geometric graphs”, arXiv:1004.2850 (2011).

Solutions 0

No solutions have been posted yet.