Speaker: Janos Pach, École Polytechnique Fédérale de Lausanne and CUNY
Title: Computing the Crossing Number of Graphs
Abstract: The rectilinear crossing number of a graph G, lcr(G), is the minimum number of crossing edges in any straight-line drawing of G. Determining or estimating lcr(G) appears to be a difficult problem, and deciding if lcr(G)<k is known to be NP-hard. Even the asymptotic behavior of the complete graph with n vertices is unknown, as n tends to infinity.
We present a deterministic n^{2+o(1)}-time algorithm that finds a straight-line drawing of any n-vertex graph G with lcr(G) + o(n^4) crossings. Together with the well-known Crossing Lemma due to Ajtai et al. and Leighton, this result implies that for any dense graph G, one can efficiently find a straight-line drawing of G with (1 + o(1))lcr(G) crossings edges. The proof is based on a geometric and on a graph theoretical partition result. Joint work with Jacob Fox and Andrew Suk.