1 citations · 1 across the 2 of their papers we have counts for
4 papers
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)…
Twin-width and Limits of Tractability of FO Model Checking on Geometric Graphs
Petr Hliněný, Filip Pokrývka
The complexity of the problem of deciding properties expressible in FO logic on graphs -- the FO model checking problem (parameterized by the respective FO formula), is well-unders…
Clique-Width of Point Configurations
Onur Çağırıcı, Petr Hliněný, Filip Pokrývka +1
While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose…
FO model checking of geometric graphs
Petr Hliněný, Filip Pokrývka, Bodhayan Roy
Over the past two decades the main focus of research into first-order (FO) model checking algorithms has been on sparse relational structures - culminating in the FPT algorithm by…