2026-07-25T03:00:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22167 2024-12-04T06:53:44Z ddc:004 open_access

Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width) Hliněný, Petr Khazaliya, Liana Graph Drawing Crossing Number Tree-width Path-width Crossing Number is a celebrated problem in graph drawing. It is known to be NP-complete since the 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, for simple graphs of path-width 13 and 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 graph decompositions of bounded width, what has been a "tantalizing open problem" [S. Cabello, Hardness of Approximation for Crossing Number, 2013] till now. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Hliněný and Liana Khazaliya 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.40 urn:nbn:de:0030-drops-221677 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.40 eng https://creativecommons.org/licenses/by/4.0/legalcode