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.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne