2-Trees as Subgraphs of Rectangle Intersection Graphs

A rectangle intersection graph is a graph whose vertices are rectangles in which two rectangles are adjacent if and only if they intersect. A 2-tree is any graph that can be obtained by starting with a single edge and repeatedly adding a vertex adjacent to both endpoints of an existing edge. In this talk I will prove that, for every natural number $k$, there exists a 2-tree $T_k$ such that any rectangle intersection graph that contains a subgraph isomorphic to $T_k$ also contains a clique of size $k$. I will also give some background and motivation for studying these kinds of problems.

This is joint work with Vida Dujmović, Gwenaël Joret, and David Wood.