Crossing-pairs conjecture for topological graphs

From papers

A topological graph is a graph drawn in the plane with vertices represented by points and edges by curves connecting their endpoints; two edges cross when their curves intersect away from common endpoints. The crossing-pairs conjecture. In every topological graph with nn vertices and m4nm\geq 4n edges, there are two disjoint sets of edges, each of cardinality

Ω(m2n2logmn),\Omega\left(\frac{m^2}{n^2\log\frac{m}{n}}\right),

such that every edge in one set crosses every edge in the other. The claimed bound would be tight and is presented as a consequence of the sharper extremal conjecture.

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

Jacob Fox and Janos Pach, “Applications of a new separator theorem for string graphs”, arXiv:1302.7228 (2013).

Solutions 0

No solutions have been posted yet.