research
∙
08/25/2023
Min-k-planar Drawings of Graphs
The study of nonplanar drawings of graphs with restricted crossing confi...
share
research
∙
07/06/2023
The grid-minor theorem revisited
We prove that for every planar graph X of treedepth h, there exists a po...
research
∙
06/09/2023
Proof of the Clustered Hadwiger Conjecture
Hadwiger's Conjecture asserts that every K_h-minor-free graph is properl...
research
∙
03/27/2023
The Excluded Tree Minor Theorem Revisited
We prove that for every tree T of radius h, there is an integer c such t...
research
∙
05/30/2022
Linear versus centred chromatic numbers
We prove that the linear chromatic number of any k× k pseudogrid is Ω(k)...
research
∙
02/17/2022
An Optimal Algorithm for Product Structure in Planar Graphs
The Product Structure Theorem for planar graphs (Dujmović et al.JACM, 67...
research
∙
05/05/2021
2× n Grids have Unbounded Anagram-Free Chromatic Number
We show that anagram-free vertex colouring a 2× n square grid requires a...
research
∙
05/04/2021
Separating layered treewidth and row treewidth
Layered treewidth and row treewidth are recently introduced graph parame...
research
∙
11/09/2020
Stack-number is not bounded by queue-number
We describe a family of graphs with queue-number at most 4 but unbounded...
research
∙
10/12/2020
Sparse universal graphs for planarity
We show that for every integer n≥ 1 there exists a graph G_n with (1+o(1...
research
∙
07/13/2020
Asymptotically Optimal Vertex Ranking of Planar Graphs
A (vertex) ℓ-ranking is a labelling φ:V(G)→ℕ of the vertices of a graph ...
research
∙
04/07/2020
Two Results on Layered Pathwidth and Linear Layouts
Layered pathwidth is a new graph parameter studied by Bannister et al (2...
research
∙
04/06/2020
A Fast Algorithm for the Product Structure of Planar Graphs
Dujmović et al (FOCS2019) recently proved that every planar graph G is a...
research
∙
03/09/2020
Adjacency Labelling for Planar Graphs (and Beyond)
We show that there exists an adjacency labelling scheme for planar graph...
research
∙
02/13/2020
Drawing Graphs as Spanners
We study the problem of embedding graphs in the plane as good geometric ...
research
∙
07/11/2019
The structure of k-planar graphs
Dujmović et al. (FOCS 2019) recently proved that every planar graph is a...
research
∙
04/09/2019
Planar Graphs have Bounded Queue-Number
We show that planar graphs have bounded queue-number, thus proving a con...
research
∙
03/06/2019
Encoding 3SUM
We consider the following problem: given three sets of real numbers, out...
research
∙
01/17/2019
Queue Layouts of Graphs with Bounded Degree and Bounded Genus
We prove that graphs with bounded degree and bounded Euler genus have bo...
research
∙
12/24/2018
Near-Optimal O(k)-Robust Geometric Spanners
For any constants d> 1, ϵ >0, t>1, and any n-point set P⊂R^d, we show th...
research
∙
12/17/2018
Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
research
∙
10/19/2018
Minor-closed graph classes with bounded layered pathwidth
We prove that a minor-closed class of graphs has bounded layered pathwid...
research
∙
03/09/2018
Geodesic Obstacle Representation of Graphs
An obstacle representation of a graph is a mapping of the vertices onto ...
research
∙
08/31/2017
EPG-representations with small grid-size
In an EPG-representation of a graph G each vertex is represented by a pa...
research
∙
06/30/2017
More Turán-Type Theorems for Triangles in Convex Point Sets
We study the following family of problems: Given a set of n points in co...
research
∙
01/15/2010