Petr Hliněný

Petr Hliněný, Liana Khazaliya

The crossing number of a graph is the minimum number of edge crossings that a graph can have when drawn in the plane. Determining this number, known as the Crossing Number problem, is a celebrated problem in combinatorial optimization. It has been known to be NP-complete since the 1980s, and already showing its fixed-parameter tractability when parameterized by the vertex cover number required fairly involved techniques. In this paper, we prove that computing the crossing number exactly remains NP-hard even for graphs of path-width 12 (and as a result, for simple graphs of path-width 13 and tree-width 9). These results highlight that, although both path- and tree-decompositions have been highly successful tools in many graph algorithm scenarios, general crossing number computation is unlikely (under P $\neq$ NP) to be successfully tackled using graph decompositions of bounded width -- a question that had remained a 'tantalizing open problem' [S. Cabello, Hardness of Approximation for Crossing Number, 2013] till now.

Petr Hliněný, Jan Jedelský

We introduce, for every surface Σ, a two-way connection between FO transductions (first-order logical transformations) of the graphs embeddable in Σ and a certain variant of fan-crossing drawings of graphs in Σ. If the target graphs drawn in Σ are additionally of bounded maximum degree, then the restriction on drawings is simply to have a bounded number of crossings per edge (such as being k-planar for fixed k if Σ is the plane). For graph classes, this connection allows us to derive non-transducibility results from nonexistence of the said drawings and, conversely, from nonexistence of a transduction to derive nonexistence of the said drawings. For example, the class of 3D-grids is not k-planar for any fixed k. We hope that this connection will help to draw a path to a possible proof that not all toroidal graphs are transducible from planar graphs. The result is based on a very recent characterization of weakly sparse FO transductions of classes of bounded expansion by [Gajarský, Gładkowski, Jedelský, Pilipczuk and Toruńczyk, arXiv:2505.15655].

Jakub Balabán, Petr Hliněný, Jan Jedelský et al.

Motivated by recently discovered connections between matroid depth measures and block-structured integer programming [ICALP 2020, 2022], we undertake a systematic study of recursive depth parameters for matrices and matroids, aiming to unify recently introduced and scattered concepts. We propose a general framework that naturally yields eight different depth measures for matroids, prove their fundamental properties and relationships, and relate them to two established notions in the field: matroid branch-depth and a newly introduced natural depth counterpart of matroid tree-width. In particular, we show that six of our eight measures are mutually functionally inequivalent, and among these, one is functionally equivalent to matroid branch-depth and another to matroid tree-depth. Importantly, we also prove that these depth measures coincide on matroids and on matrices over any field, which is (somehow surprisingly) not a trivial task. Finally, we provide a comparison between the matroid parameters and classical depth measures of graphs.