Intersection Graphs with and without Product Structure

A graph class G admits product structure if there exists a constant k such that every G G is a subgraph of H P for a path P and some graph H of treewidth k. Famously, the class of planar graphs, as well as many beyond-planar graph classes are known to admit product structure. However, we have only few tools to prove the absence of product structure, and hence know of only a few interesting examples of classes. Motivated by the transition between product structure and no product structure, we investigate subclasses of intersection graphs in the plane (e. g. , disk intersection graphs) and present necessary and sufficient conditions for these to admit product structure. Specifically, for a set S R² (e. g. , a disk) and a real number 0, 1, we consider intersection graphs of -free homothetic copies of S. That is, each vertex v is a homothetic copy of S of which at least an -portion is not covered by other vertices, and there is an edge between u and v if and only if u v. For = 1 we have contact graphs, which are in most cases planar, and hence admit product structure. For = 0 we have (among others) all complete graphs, and hence no product structure. In general, there is a threshold value ^* (S) 0, 1 such that -free homothetic copies of S admit product structure for all > ^* (S) and do not admit product structure for all < ^* (S). We show for a large family of sets S, including all triangles and all trapezoids, that it holds ^* (S) = 1, i. e. , we have no product structure, except for the contact graphs (when = 1). For other sets S, including regular n-gons for infinitely many values of n, we show that 0 < ^* (S) < 1 by proving upper and lower bounds.