research
∙
07/04/2023
Sparse Graphs of Twin-width 2 Have Bounded Tree-width
Twin-width is a structural width parameter introduced by Bonnet, Kim, Th...
share
research
∙
06/15/2023
Minimizing an Uncrossed Collection of Drawings
In this paper, we introduce the following new concept in graph drawing. ...
research
∙
06/06/2023
Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs
In this paper we deal with the problem of computing the exact crossing n...
research
∙
03/17/2023
Stack and Queue Numbers of Graphs Revisited
A long-standing question of the mutual relation between the stack and qu...
research
∙
12/11/2022
Beyond circular-arc graphs – recognizing lollipop graphs and medusa graphs
In 1992 Biró, Hujter and Tuza introduced, for every fixed connected grap...
research
∙
10/16/2022
Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar
The structural parameter twin-width was introduced by Bonnet et al. in [...
research
∙
04/28/2022
Twin-width and Limits of Tractability of FO Model Checking on Geometric Graphs
The complexity of the problem of deciding properties expressible in FO l...
research
∙
04/25/2022
Graph Product Structure for h-Framed Graphs
Graph product structure theory expresses certain graphs as subgraphs of ...
research
∙
02/28/2022
Parameterised Partially-Predrawn Crossing Number
Inspired by the increasingly popular research on extending partial graph...
research
∙
02/25/2022
Automorphism Group of Marked Interval Graphs in FPT
An interval graph is the intersection graph of a set of intervals on the...
research
∙
02/25/2022
Twin-width and Transductions of Proper k-Mixed-Thin Graphs
The new graph parameter twin-width, recently introduced by Bonnet, Kim, ...
research
∙
11/21/2021
Isomorphism Testing for T-graphs in FPT
A T-graph (a special case of a chordal graph) is the intersection graph ...
research
∙
06/29/2021
Twin-Width is Linear in the Poset Width
Twin-width is a new parameter informally measuring how diverse are the n...
research
∙
03/28/2021
Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
We initiate the study of computational complexity of graph coverings, ak...
research
∙
04/05/2020
Clique-Width of Point Configurations
While structural width parameters (of the input) belong to the standard ...
research
∙
06/14/2019
Exact Crossing Number Parameterized by Vertex Cover
We prove that the exact crossing number of a graph can be efficiently co...
research
∙
06/05/2019
On Colourability of Polygon Visibility Graphs
We study the problem of colouring visibility graphs of polygons. In part...
research
∙
04/18/2019
On conflict-free chromatic guarding of simple polygons
We study the problem of colouring the vertices of a polygon, such that e...
research
∙
03/13/2019
Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12
We study c-crossing-critical graphs, which are the minimal graphs that r...
research
∙
05/04/2018
A New Perspective on FO Model Checking of Dense Graph Classes
We study the first-order (FO) model checking problem of dense graphs, na...
research
∙
03/05/2018
Structure and generation of crossing-critical graphs
We study c-crossing-critical graphs, which are the minimal graphs that r...
research
∙
09/12/2017