Title: A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs Show Chinese title

Title: 计算块图补图的箱维数和阈值维数的多项式算法

Abstract: The boxicity of a graph $G$ is the minimum dimension $d$ that admits a representation of $G$ as the intersection graph of a family of axis-parallel boxes in $\mathbb{R}^d$. Computing boxicity is an NP-hard problem, and there are few known graph classes for which it can be computed in polynomial time. One such class is the class of block graphs. A block graph is a graph in which every maximal $2$-connected component is a clique. Since block graphs are known to have boxicity at most two, computing their boxicity amounts to the linear-time interval graph recognition problem. On the other hand, complements of block graphs have unbounded boxicity, yet we show that there is also a polynomial algorithm that computes the boxicity of complements of block graphs. An adaptation of our approach yields a polynomial algorithm for computing the threshold dimension of the complements of block graphs, which for general graphs is an NP-hard problem. Our method suggests a general technique that may show the tractability of similar problems on block-restricted graph classes. Show Chinese abstract

Abstract: 图 $G$ 的盒数是使 $G$ 能够作为轴对齐长方体族的交集图在 $\mathbb{R}^d$ 中表示的最小维度 $d$。 计算盒数是一个 NP 难问题，且已知的可以多项式时间计算盒数的图类很少。 其中一个这样的类是块图类。 块图是每个极大 $2$-连通分量都是团的图。 由于已知块图的盒数最多为二，计算它们的盒数就相当于线性时间区间图识别问题。 另一方面，块图的补图具有无界的盒数，但我们证明也存在一个多项式算法可以计算块图补图的盒数。 我们方法的一个改编版本可得到一个多项式算法来计算块图补图的阈值维数，而对于一般图来说这是一个 NP 难问题。 我们的方法提示了一种通用技术，可能显示在块限制图类上的类似问题的可解性。