Computing the Crossing Number of Graphs

MAR 16, 2017 | 4:15 PM



The Graduate Center
365 Fifth Avenue




March 16, 2017: 4:15 PM




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.