73 citations · 387 across the 61 of their papers we have counts for
4 papers · 1 filter
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…
Planar graphs have bounded queue-number
Vida Dujmović, Gwenaël Joret, Piotr Micek +3
We show that planar graphs have bounded queue-number, thus proving a conjecture of Heath, Leighton and Rosenberg from 1992. The key to the proof is a new structural tool called lay…
Improved Methods For Generating Quasi-Gray Codes
Dana Jansens, Prosenjit Bose, Paz Carmi +3
Consider a sequence of bit strings of length d, such that each string differs from the next in a constant number of bits. We call this sequence a quasi-Gray code. We examine the pr…
A Characterization of the Degree Sequences of 2-Trees
Prosenjit Bose, Vida Dujmović, Danny Krizanc +4
A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose neighbours are adjacent, and Gǐs a 2-tree. A characterization of the degree sequences of 2-trees is given. Th…