Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width)

Abstract

Full Citation:

Petr Hlinen'y, Liana Khazaliya. Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width). 35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia (Juli'an Mestre and Anthony Wirth), volume 322 of LIPIcs, pages 40:1-40:15, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

Liana Khazaliya

Liana Khazaliya is a Project Assistant at the Algorithms and Complexity Group.