
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

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

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

Universal Reconfiguration of FacetConnected Modular Robots by Pivots: The O(1) Musketeers
We present the first universal reconfiguration algorithm for transformin...
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 nonrepetitive chromatic number
A colouring of a graph is "nonrepetitive" if for every path of even orde...
read it

Planar Graphs have Bounded QueueNumber
We show that planar graphs have bounded queuenumber, thus proving a con...
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

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

Pole Dancing: 3D Morphs for Tree Drawings
We study the question whether a crossingfree 3D morph between two strai...
read it

Tight Upper Bounds on the Crossing Number in a MinorClosed Class
The crossing number of a graph is the minimum number of crossings in a d...
read it

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...
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

Thickness and Antithickness of Graphs
This paper studies questions about duality between crossings and noncro...
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
Vida Dujmovic
is this you? claim profile