73 citations · 427 across the 49 of their papers we have counts for
4 papers · 1 filter
Product structure extension of the Alon--Seymour--Thomas theorem
Marc Distel, Vida Dujmović, David Eppstein +6
Alon, Seymour and Thomas [1990] proved that every -vertex graph excluding as a minor has treewidth less than . Illingworth, Scott and Wood [2022] recently…
Bounded-Degree Planar Graphs Do Not Have Bounded-Degree Product Structure
Vida Dujmović, Gwenaël Joret, Piotr Micek +2
Product structure theorems are a collection of recent results that have been used to resolve a number of longstanding open problems on planar graphs and related graph classes. One…
Treedepth vs circumference
Marcin Briański, Gwenaël Joret, Konrad Majewski +3
The circumference of a graph is the length of a longest cycle in , or if has no cycle. Birmelé (2003) showed that the treewidth of a graph is at most its c…
Boolean dimension and dim-boundedness: Planar cover graph with a zero
Heather Smith Blake, Piotr Micek, William T. Trotter
In 1989, Nešetřil and Pudlák posed the following challenging question: Do planar posets have bounded Boolean dimension? We show that every poset with a planar cover graph and a uni…