5 papers · 1 filter
Erdős--Pósa property of cycles that are far apart
Vida Dujmović, Gwenaël Joret, Piotr Micek +1
We prove that there exist functions such that for all nonnegative integers and , for every graph , either contains cycles such that…
On -planar Graphs without Short Cycles
Michael A. Bekos, Prosenjit Bose, Aaron Büngener +6
We study the impact of forbidding short cycles to the edge density of -planar graphs; a -planar graph is one that can be drawn in the plane with at most crossings per edg…
Planar graphs in blowups of fans
Marc Distel, Vida Dujmović, Gwenaël Joret +3
We show that every -vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order . Equivalently,…
Vertex Ranking of Degenerate Graphs
John Iacono, Piotr Micek, Pat Morin +1
An -vertex-ranking of a graph is a colouring of the vertices of with integer colours so that in any connected subgraph of with diameter at most , there…
Grid Minors and Products
Vida Dujmović, Pat Morin, David R. Wood +1
Motivated by recent developments regarding the product structure of planar graphs, we study relationships between treewidth, grid minors, and graph products. We show that the Carte…