Pat Morin

collaborators

4 papers

math.CO2025

Separation Number and Treewidth, Revisited

Hussein Houdrouge, Babak Miraftab, Pat Morin

We give a constructive proof of the fact that the treewidth of a graph $G$ is bounded by a linear function of the separation number of $G$ .

cs.CG2024

Free Sets in Planar Graphs: History and Applications

Vida Dujmović, Pat Morin

A subset $S$ of vertices in a planar graph $G$ is a free set if, for every set $P$ of $∣ S ∣$ points in the plane, there exists a straight-line crossing-free drawing of $G$ in which…

math.CO2024

Tight bound for the Erdős-Pósa property of tree minors

Vida Dujmović, Gwenaël Joret, Piotr Micek +1

Let $T$ be a tree on $t$ vertices. We prove that for every positive integer $k$ and every graph $G$ , either $G$ contains $k$ pairwise vertex-disjoint subgraphs each having a $T$ mi…

math.PR2024

Patricia's Bad Distributions

Louigi Addario-Berry, Pat Morin, Ralph Neininger

The height of a random PATRICIA tree built from independent, identically distributed infinite binary strings with arbitrary diffuse probability distribution $μ$ on $\{0,1\}^\mathbb…