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
∙
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
∙
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
∙
03/09/2020
Adjacency Labelling for Planar Graphs (and Beyond)
We show that there exists an adjacency labelling scheme for planar graph...
research
∙
08/21/2019
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers
We present the first universal reconfiguration algorithm for transformin...
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/10/2019
Planar graphs have bounded nonrepetitive chromatic number
A colouring of a graph is "nonrepetitive" if for every path of even orde...
research
∙
04/09/2019
Planar Graphs have Bounded Queue-Number
We show that planar graphs have bounded queue-number, thus proving a con...
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
∙
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
∙
08/31/2018
Pole Dancing: 3D Morphs for Tree Drawings
We study the question whether a crossing-free 3D morph between two strai...
research
∙
07/31/2018
Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
The crossing number of a graph is the minimum number of crossings in a d...
research
∙
06/15/2018
A note on choosability with defect 1 of graphs on surfaces
This note proves that every graph of Euler genus μ is 2 + √(3μ + 3) --c...
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
∙
08/16/2017
Thickness and Antithickness of Graphs
This paper studies questions about duality between crossings and non-cro...
research
∙
06/30/2017