On refined hardness of the graph crossing number

Orateur : Petr Hliněný
30 Avril 2024 à 14:00 ; lieu : Salle de séminaire 4B125 (bâtiment Copernic)

Minimizing the crossing number of a graph, i.e., the minimum number of pairwise edge crossings over all drawings in the plane, is a notoriously computationally hard problem.

It remains hard even under very restrictive settings of the input. We survey some the many know hardness results in this area, and, in response to a long standing open question of the area, we  present a new hardness reduction proving that the crossing number problem remains NP-complete for graphs of constant tree-width and path-width.

The latter result is a joint work with Liana Khazaliya from TU Wien.


Salle de séminaire 4B125 (bâtiment Copernic)

5 Boulevard Descartes 77420 Champs-sur-Marne