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.

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).

View abstract PDF