30 citations · 90 across the 12 of their papers we have counts for
5 papers · 1 filter
Stack-number is not bounded by queue-number
Vida Dujmović, David Eppstein, Robert Hickingbotham +2
We describe a family of graphs with queue-number at most 4 but unbounded stack-number. This resolves open problems of Heath, Leighton and Rosenberg (1992) and Blankenship and Oporo…
Asymptotically Optimal Vertex Ranking of Planar Graphs
Prosenjit Bose, Vida Dujmović, Mehrnoosh Javarsineh +1
A (vertex) -ranking is a colouring of the vertices of a graph with integer colours so that for any path of length at most , $…
Two Results on Layered Pathwidth and Linear Layouts
Vida Dujmović, Pat Morin, Céline Yelle
Layered pathwidth is a new graph parameter studied by Bannister et al (2015). In this paper we present two new results relating layered pathwidth to two types of linear layouts. Ou…
Adjacency Labelling for Planar Graphs (and Beyond)
Vida Dujmović, Louis Esperet, Gwenaël Joret +3
We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an -vertex planar graph is assigned a -bit label and the lab…
Clustered 3-Colouring Graphs of Bounded Degree
Vida Dujmović, Louis Esperet, Pat Morin +2
A (not necessarily proper) vertex colouring of a graph has "clustering" if every monochromatic component has at most vertices. We prove that planar graphs with maximum degr…