О реберной планаризации и crossing number графов

Мой доклад будет посвящён задаче нахождения «оптимального» вложения графа в плоскость, т.е. вложения с минимальным числом скрещиваний (числом пересекающихся рёбер). Сначала я кратко изложу известные результаты. В частности, я покажу, что задачу нельзя решить точно за полиномиальное время (если $P$ не равно $NP$) [Garey and Johnson 1983]. Затем мы обсудим приближённые методы её решения. Я расскажу о связи этой задачи с задачей о «рёберной планаризации» и опишу новые аппроксимационные алгоритмы для неё.
Доклад основан на совместной работе с Julia Chuzhoy и Anastasios Sidiropoulos.