
2× n Grids have Unbounded AnagramFree Chromatic Number
We show that anagramfree vertex colouring a 2× n square grid requires a...
read it

Separating layered treewidth and row treewidth
Layered treewidth and row treewidth are recently introduced graph parame...
read it

Stacknumber is not bounded by queuenumber
We describe a family of graphs with queuenumber at most 4 but unbounded...
read it

Sparse universal graphs for planarity
We show that for every integer n≥ 1 there exists a graph G_n with (1+o(1...
read it

Asymptotically Optimal Vertex Ranking of Planar Graphs
A (vertex) ℓranking is a labelling φ:V(G)→ℕ of the vertices of a graph ...
read it

Two Results on Layered Pathwidth and Linear Layouts
Layered pathwidth is a new graph parameter studied by Bannister et al (2...
read it

A Fast Algorithm for the Product Structure of Planar Graphs
Dujmović et al (FOCS2019) recently proved that every planar graph G is a...
read it

Adjacency Labelling for Planar Graphs (and Beyond)
We show that there exists an adjacency labelling scheme for planar graph...
read it

Drawing Graphs as Spanners
We study the problem of embedding graphs in the plane as good geometric ...
read it

The structure of kplanar graphs
Dujmović et al. (FOCS 2019) recently proved that every planar graph is a...
read it

Planar Graphs have Bounded QueueNumber
We show that planar graphs have bounded queuenumber, thus proving a con...
read it

Encoding 3SUM
We consider the following problem: given three sets of real numbers, out...
read it

Queue Layouts of Graphs with Bounded Degree and Bounded Genus
We prove that graphs with bounded degree and bounded Euler genus have bo...
read it

NearOptimal O(k)Robust Geometric Spanners
For any constants d> 1, ϵ >0, t>1, and any npoint set P⊂R^d, we show th...
read it

Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
read it

Minorclosed graph classes with bounded layered pathwidth
We prove that a minorclosed class of graphs has bounded layered pathwid...
read it

Geodesic Obstacle Representation of Graphs
An obstacle representation of a graph is a mapping of the vertices onto ...
read it

EPGrepresentations with small gridsize
In an EPGrepresentation of a graph G each vertex is represented by a pa...
read it

More TuránType Theorems for Triangles in Convex Point Sets
We study the following family of problems: Given a set of n points in co...
read it

Planar Visibility: Testing and Counting
In this paper we consider query versions of visibility testing and visib...
read it
Pat Morin
is this you? claim profile