5 papers · 1 filter
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,…
Rectilinear Crossing Number of Graphs Excluding Single-Crossing Graphs as Minors
Vida Dujmović, Camille La Rose
The crossing number of a graph is the minimum number of crossings in a drawing of in the plane. A rectilinear drawing of a graph represents vertices of by a set of…
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…
Connected Dominating Sets in Triangulations
Prosenjit Bose, Vida Dujmović, Hussein Houdrouge +2
We show that every -vertex triangulation has a connected dominating set of size at most . Equivalently, every vertex triangulation has a spanning tree with at least…