16 citations · 94 across the 30 of their papers we have counts for
8 papers · 1 filter
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Benjamin Bergougnoux, Jakub Gajarský, Grzegorz Guśpiel +3
Twin-width is a structural width parameter introduced by Bonnet, Kim, Thomassé and Watrigant [FOCS 2020]. Very briefly, its essence is a gradual reduction (a contraction sequence)…
Stack and Queue Numbers of Graphs Revisited
Petr Hliněný, Adam Straka
A long-standing question of the mutual relation between the stack and queue numbers of a graph, explicitly emphasized by Dujmović and Wood in 2005, was "half-answered" by Dujmović,…
Twin-width and Transductions of Proper k-Mixed-Thin Graphs
Jakub Balabán, Petr Hliněný, Jan Jedelský
The new graph parameter twin-width, introduced by Bonnet, Kim, Thomass e and Watrigant in 2020, allows for an FPT algorithm for testing all FO properties of graphs. This makes clas…
On Colourability of Polygon Visibility Graphs
Onur Çağirici, Petr Hliněný, Bodhayan Roy
We study the problem of colouring visibility graphs of polygons. In particular, for visibility graphs of simple polygons, we provide a polynomial algorithm for 4-colouring, and pro…
On Degree Properties of Crossing-Critical Families of Graphs
Drago Bokal, Mojca Bračič, Marek Derňár +1
Answering an open question from 2007, we construct infinite -crossing-critical families of graphs that contain vertices of any prescribed odd degree, for any sufficiently large~…
Structure and generation of crossing-critical graphs
Zdeněk Dvořák, Petr Hliněný, Bojan Mohar
We study -crossing-critical graphs, which are the minimal graphs that require at least edge-crossings when drawn in the plane. For there are only two such graphs witho…