research
∙
08/23/2023
Cliquewidth and dimension
We prove that every poset with bounded cliquewidth and with sufficiently...
share
research
∙
07/01/2023
Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
Let d be a positive integer. For a finite set X ⊆ℝ^d, we define its inte...
research
∙
04/04/2023
Dynamic treewidth
We present a data structure that for a dynamic graph G that is updated b...
research
∙
02/26/2023
Partitioning edges of a planar graph into linear forests and a matching
We show that the edges of any planar graph of maximum degree at most 9 c...
research
∙
01/31/2023
Flipper games for monadically stable graph classes
A class of graphs 𝒞 is monadically stable if for any unary expansion 𝒞 o...
research
∙
10/26/2022
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
We prove that Graph Isomorphism and Canonization in graphs excluding a f...
research
∙
10/26/2022
Highly unbreakable graph with a fixed excluded minor are almost rigid
A set X ⊆ V(G) in a graph G is (q,k)-unbreakable if every separation (A,...
research
∙
05/30/2022
Independence number of intersection graphs of axis-parallel segments
We prove that for any triangle-free intersection graph of n axis-paralle...
research
∙
01/23/2022
Bounding generalized coloring numbers of planar graphs using coin models
We study Koebe orderings of planar graphs: vertex orderings obtained by ...
research
∙
03/31/2021
An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
In the Disjoint Paths problem, the input is an undirected graph G on n v...
research
∙
09/28/2020
Quasi-polynomial-time algorithm for Independent Set in P_t-free graphs via shrinking the space of induced paths
In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showe...
research
∙
07/15/2020
Rankwidth meets stability
We study two notions of being well-structured for classes of graphs that...
research
∙
03/27/2020
Covering minimal separators and potential maximal cliques in P_t-free graphs
A graph is called P_t-free if it does not contain a t-vertex path as an ...
research
∙
04/24/2019
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs
We consider the classic Facility Location problem on planar graphs (non-...
research
∙
10/04/2018
