8 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…