16 citations · 94 across the 30 of their papers we have counts for
13 papers · 1 filter
Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs
Petr Hliněný
In this paper we deal with the problem of computing the exact crossing number of almost planar graphs and the closely related problem of computing the exact anchored crossing numbe…
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…
Twin-Width is Linear in the Poset Width
Jakub Balabán, Petr Hliněný
Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digr…
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
Jan Bok, Jiří Fiala, Petr Hliněný +2
We initiate the study of computational complexity of graph coverings, aka locally bijective graph homomorphisms, for {\em graphs with semi-edges}. The notion of graph covering is a…
Exact Crossing Number Parameterized by Vertex Cover
Petr Hliněný, Abhisekh Sankaran
We prove that the exact crossing number of a graph can be efficiently computed for simple graphs having bounded vertex cover. In more precise words, Crossing Number is in FPT when…
On Hardness of the Joint Crossing Number
Petr Hliněný, Gelasio Salazar
The Joint Crossing Number problem asks for a simultaneous embedding of two disjoint graphs into one surface such that the number of edge crossings (between the two graphs) is minim…