83 citations · 606 across the 54 of their papers we have counts for
64 papers
Free Sets in Planar Graphs: History and Applications
Vida Dujmović, Pat Morin
A subset of vertices in a planar graph is a free set if, for every set of points in the plane, there exists a straight-line crossing-free drawing of in which…
Tight bound for the Erdős-Pósa property of tree minors
Vida Dujmović, Gwenaël Joret, Piotr Micek +1
Let be a tree on vertices. We prove that for every positive integer and every graph , either contains pairwise vertex-disjoint subgraphs each having a mi…
Face flips in origami tessellations
Hugo A. Akitaya, Vida Dujmovi, David Eppstein +3
Given a flat-foldable origami crease pattern (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment …
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The Musketeers
Hugo A. Akitaya, Esther M. Arkin, Mirela Damian +8
We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precise…
Planar graphs have bounded nonrepetitive chromatic number
Vida Dujmović, Louis Esperet, Gwenaël Joret +2
A colouring of a graph is "nonrepetitive" if for every path of even order, the sequence of colours on the first half of the path is different from the sequence of colours on the se…
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…