Crossing Number is NP-hard for Constant Path-width (and Tree-width)
<|reference_start|>Crossing Number is NP-hard for Constant Path-width (and Tree-width): Crossing Number is a celebrated problem in graph drawing. It is known to be NP-complete since 1980s, and fairly involved techniques were already required to show its fixed-parameter tractability when parameterized by the vertex cover number. In this paper we prove that computing exactly the crossing number is NP-hard even for graphs of path-width 12 (and as a result, even of tree-width 9). Thus, while tree-width and path-width have been very successful tools in many graph algorithm scenarios, our result shows that general crossing number computations unlikely (under P!=NP) could be successfully tackled using bounded width of graph decompositions, which has been a 'tantalizing open problem' [S. Cabello, Hardness of Approximation for Crossing Number, 2013] till now.<|reference_end|>
@article{hliněný2024crossing,
    title={Crossing Number is NP-hard for Constant Path-width (and Tree-width)},
    author={Petr Hlinv{e}n'y and Liana Khazaliya},
    journal={arXiv preprint arXiv:2406.18933},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.18933},
    primaryClass={cs.CG cs.DM}
}