Disjoint crossing families conjecture for geometric graphs
Disjoint crossing families conjecture for geometric graphs
A geometric graph is a graph drawn in the plane with vertices represented by points and edges as straight-line segments. For integers , a -crossing family is a pair of edge subsets such that , , the edges in each subset are pairwise crossing, and every edge in is disjoint from every edge in . Disjoint crossing families conjecture. Given fixed constants , there exists a constant such that any geometric graph on vertices with no -crossing family has at most edges. The conjecture is an extremal question about forbidden crossing and disjointness patterns in geometric graphs. The case is proved with an 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
Sign in to submit a solution.
No solutions have been posted yet.