Vida Dujmovic | DeepAI

DeepAI AI Chat

Featured Co-authors

Erik D. Demaine
75 publications
David Eppstein
67 publications
Therese Biedl
39 publications
Giuseppe Liotta
39 publications
Fabrizio Montecchiani
37 publications
Prosenjit Bose
34 publications
Michael Kaufmann
34 publications
Torsten Ueckerdt
34 publications
Ken-ichi Kawarabayashi
33 publications
Gwenaël Joret
32 publications
Matias Korman
29 publications

∙ 08/25/2023

Min-k-planar Drawings of Graphs

The study of nonplanar drawings of graphs with restricted crossing confi...

0 Carla Binucci, et al. ∙

∙ 07/06/2023

The grid-minor theorem revisited

We prove that for every planar graph X of treedepth h, there exists a po...

0 Vida Dujmovic, et al. ∙

∙ 06/09/2023

Proof of the Clustered Hadwiger Conjecture

Hadwiger's Conjecture asserts that every K_h-minor-free graph is properl...

0 Vida Dujmovic, et al. ∙

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

0 Vida Dujmovic, et al. ∙

∙ 05/30/2022

Linear versus centred chromatic numbers

We prove that the linear chromatic number of any k× k pseudogrid is Ω(k)...

0 Prosenjit Bose, et al. ∙

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

0 Saman Bazarghani, et al. ∙

∙ 05/04/2021

Separating layered treewidth and row treewidth

Layered treewidth and row treewidth are recently introduced graph parame...

0 Prosenjit Bose, et al. ∙

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

0 Vida Dujmovic, et al. ∙

∙ 07/13/2020

Asymptotically Optimal Vertex Ranking of Planar Graphs

A (vertex) ℓ-ranking is a labelling φ:V(G)→ℕ of the vertices of a graph ...

0 Prosenjit Bose, et al. ∙

∙ 04/07/2020

Two Results on Layered Pathwidth and Linear Layouts

Layered pathwidth is a new graph parameter studied by Bannister et al (2...

0 Vida Dujmovic, et al. ∙

∙ 03/09/2020

Adjacency Labelling for Planar Graphs (and Beyond)

We show that there exists an adjacency labelling scheme for planar graph...

0 Vida Dujmovic, et al. ∙

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

0 Hugo A. Akitaya, et al. ∙

∙ 07/11/2019

The structure of k-planar graphs

Dujmović et al. (FOCS 2019) recently proved that every planar graph is a...

0 Vida Dujmovic, et al. ∙

∙ 04/10/2019

Planar graphs have bounded nonrepetitive chromatic number

A colouring of a graph is "nonrepetitive" if for every path of even orde...

0 Vida Dujmovic, et al. ∙

∙ 04/09/2019

Planar Graphs have Bounded Queue-Number

We show that planar graphs have bounded queue-number, thus proving a con...

0 Vida Dujmovic, et al. ∙

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

0 Vida Dujmovic, et al. ∙

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

0 Prosenjit Bose, et al. ∙

∙ 10/19/2018

Minor-closed graph classes with bounded layered pathwidth

We prove that a minor-closed class of graphs has bounded layered pathwid...

0 Vida Dujmovic, et al. ∙

∙ 08/31/2018

Pole Dancing: 3D Morphs for Tree Drawings

We study the question whether a crossing-free 3D morph between two strai...

0 Elena Arseneva, et al. ∙

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

0 Vida Dujmovic, et al. ∙

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

0 Vida Dujmovic, et al. ∙

∙ 03/09/2018

Geodesic Obstacle Representation of Graphs

An obstacle representation of a graph is a mapping of the vertices onto ...

0 Prosenjit Bose, et al. ∙

∙ 08/31/2017

EPG-representations with small grid-size

In an EPG-representation of a graph G each vertex is represented by a pa...

0 Therese Biedl, et al. ∙

∙ 08/16/2017

Thickness and Antithickness of Graphs

This paper studies questions about duality between crossings and non-cro...

0 Vida Dujmovic, et al. ∙

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

0 Boris Aronov, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world