2025/10/02 by Caoduro, Marco, Evans, Will, Gaede, Tao
#05C62 (primary) 05C10 #05C85 (secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.02199
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 ℝ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.