Title: Intersection Graphs with and without Product Structure Show Chinese title

Title: 带有和不带乘积结构的交图

Abstract: A graph class $\mathcal{G}$ admits product structure if there exists a constant $k$ such that every $G \in \mathcal{G}$ is a subgraph of $H \boxtimes 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 \subset \mathbb{R}^2$ (e.g., a disk) and a real number $\alpha \in [0,1]$, we consider intersection graphs of $\alpha$-free homothetic copies of $S$. That is, each vertex $v$ is a homothetic copy of $S$ of which at least an $\alpha$-portion is not covered by other vertices, and there is an edge between $u$ and $v$ if and only if $u \cap v \neq \emptyset$. For $\alpha = 1$ we have contact graphs, which are in most cases planar, and hence admit product structure. For $\alpha = 0$ we have (among others) all complete graphs, and hence no product structure. In general, there is a threshold value $\alpha^*(S) \in [0,1]$ such that $\alpha$-free homothetic copies of $S$ admit product structure for all $\alpha > \alpha^*(S)$ and do not admit product structure for all $\alpha < \alpha^*(S)$. We show for a large family of sets $S$, including all triangles and all trapezoids, that it holds $\alpha^*(S) = 1$, i.e., we have no product structure, except for the contact graphs (when $\alpha= 1$). For other sets $S$, including regular $n$-gons for infinitely many values of $n$, we show that $0 < \alpha^*(S) < 1$ by proving upper and lower bounds. Show Chinese abstract

Abstract: A graph class $\mathcal{G}$ admits product structure if there exists a constant $k$ such that every $G \in \mathcal{G}$ is a subgraph of $H \boxtimes 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. 具体来说，对于一个集合$S \subset \mathbb{R}^2$（例如，一个圆盘）和一个实数$\alpha \in [0,1]$，我们考虑$\alpha$-自由的与$S$相似变换的交图。 也就是说，每个顶点$v$是$S$的相似缩放副本，其中至少有一个$\alpha$部分未被其他顶点覆盖，并且当且仅当$u \cap v \neq \emptyset$时，$u$和$v$之间有一条边。对于$\alpha = 1$我们有接触图，这些图在大多数情况下是平面的，因此具有乘积结构。 对于$\alpha = 0$我们有（除其他外）所有完全图，因此没有乘积结构。 一般来说，存在一个阈值$\alpha^*(S) \in [0,1]$，使得对于所有$\alpha$的无相似副本的$S$，当$\alpha > \alpha^*(S)$时，它们具有乘积结构，而对于所有$\alpha < \alpha^*(S)$时则不具有乘积结构。 我们证明对于一大类集合$S$，包括所有三角形和所有梯形，成立$\alpha^*(S) = 1$，即除了接触图（当$\alpha= 1$时）外，没有乘积结构。对于其他集合$S$，包括正$n$-边形在无限多个$n$值的情况下，我们通过证明上下界来证明$0 < \alpha^*(S) < 1$。