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

Abstract

Full Citation:

Petr Hlinený, 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án Mestre, Anthony Wirth, eds.), 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.