## View abstract

### Plenary talk

Wednesday, July 21, 13:30 ~ 14:30 UTC-3

## Towards Better Algorithms for Graph Crossing Number

### Julia Chuzhoy

#### Toyota Technological Institute at Chicago, United States   -   This email address is being protected from spambots. You need JavaScript enabled to view it. document.getElementById('cloakefc78bcd27b1d360384ed11694d484f7').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addyefc78bcd27b1d360384ed11694d484f7 = 'cj&#117;l&#105;&#97;' + '&#64;'; addyefc78bcd27b1d360384ed11694d484f7 = addyefc78bcd27b1d360384ed11694d484f7 + 'tt&#105;c' + '&#46;' + '&#101;d&#117;'; var addy_textefc78bcd27b1d360384ed11694d484f7 = 'cj&#117;l&#105;&#97;' + '&#64;' + 'tt&#105;c' + '&#46;' + '&#101;d&#117;';document.getElementById('cloakefc78bcd27b1d360384ed11694d484f7').innerHTML += '<a ' + path + '\'' + prefix + ':' + addyefc78bcd27b1d360384ed11694d484f7 + '\'>'+addy_textefc78bcd27b1d360384ed11694d484f7+'<\/a>';

Graph Crossing Number is a fundamental and extensively studied problem with wide ranging applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. The problem is known to be notoriously difficult, and despite extensive work, it is still poorly understood from many different angles. In this talk we will focus on the algorithmic aspect of the problem. As the problem is known to be NP-hard, it is natural to look for efficient algorithms that solve the problem approximately. We will survey some known techniques for designing efficient (approximate) algorithms, and discuss some new promising directions in this area.

Joint work with Sepideh Mahabadi (Toyota Technological Institute at Chicago) and Zihan Tan (University of Chicago).