Computer Science Seminar
Andrew Suk
UIC
Approximating the rectilinear crossing number
Abstract: A straight-line drawing of a graph $G$ is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph $G$, $\overline{cr}(G)$, is the minimum number of pairs of crossing edges in any straight-line drawing of $G$. Determining or estimating $\overline{cr}(G)$ appears to be a difficult problem, and deciding if $\overline{cr}(G)\leq k$ is known to be NP-hard. In fact, the asymptotic behavior of $\overline{cr}(K_n)$ is still unknown.
In this talk, we present a deterministic $n^{2+o(1)}$-time algorithm that finds a straight-line drawing of any $n$-vertex graph $G$ with $\overline{cr}(G) + o(n^4)$ pairs of crossing edges. Together with the well-known Crossing Lemma due to Ajtai et al.~and Leighton, this result implies that for any dense $n$-vertex graph $G$, one can efficiently find a straight-line drawing of $G$ with $(1 + o(1))\overline{cr}(G)$ pairs of crossing edges. This is joint work with Jacob Fox and Janos Pach.
Monday October 3, 2016 at 2:00 PM in SEO 612