## View abstract

#### Conference abstracts

Plenary talk

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

## Towards Better Algorithms for Graph Crossing Number

### Julia Chuzhoy

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.