12 papers
Product Structure Meets Track Layouts
Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný +1
A track layout of a graph is a partition of its vertices into linearly ordered independent sets, called tracks, such that no two edges between the same pair of tracks cross. Given…
Conflict-Free Coloring Planar Graphs with 4 Colors
Petr Hliněný, Lukáš Málik
We efficiently conflict-free color every planar graph with 4 colors. An (open-neighborhood) conflict-free coloring assigns colors to vertices in a way that every vertex v has a nei…
Measuring Depth of Matroids
Jakub Balabán, Petr Hliněný, Jan Jedelský +1
Motivated by recently discovered connections between matroid depth measures and block-structured integer programming [ICALP 2020, 2022], we undertake a systematic study of recursiv…
Transductions of Graph Classes Admitting Product Structure
Petr Hliněný, Jan Jedelský
In a quest to thoroughly understand the first-order transduction hierarchy of hereditary graph classes, some questions in particular stand out; such as, what properties hold for gr…
A Unified FPT Framework for Crossing Number Problems
Éric Colin de Verdière, Petr Hliněný
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified fr…
On the Uncrossed Number of Graphs
Martin Balko, Petr Hliněný, Tomáš Masařík +3
Visualizing a graph in the plane nicely, for example, without crossings, is unfortunately not always possible. To address this problem, Masařík and Hliněný [GD 2023] recently a…
Crossing Number is NP-hard for Constant Path-width (and Tree-width)
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,…
Note on Min-k-Planar Drawings of Graphs
Petr Hliněný, Lili Ködmön
The k-planar graphs, which are (usually with small values of k such as 1, 2, 3) subject to recent intense research, admit a drawing in which edges are allowed to cross, but each on…
Twin-width of Planar Graphs; a Short Proof
Petr Hliněný
The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from the final resolution; there is a lower bound of 7 coming from a construction b…
Twin-width of Planar Graphs is at most 8, and some Related Bounds
Petr Hliněný, Jan Jedelský
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020], and has interesting applications in the areas of logic on graphs and in pa…
On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
Petr Hliněný, Michal Korbela
A recent result of Bokal et al. [Combinatorica, 2022] proved that the exact minimum value of c such that c-crossing-critical graphs do not have bounded maximum degree is c=13. The…
A Simpler Self-reduction Algorithm for Matroid Path-width
Petr Hliněný
Path-width of matroids naturally generalizes the better known parameter of path-width for graphs, and is NP-hard by a reduction from the graph case. While the term matroid path-wid…