UVictoria Discrete Math Seminar: Marco Caoduro

The boxicity of a graph G is a key graph parameter introduced by Roberts in 1969. It represents the minimum dimension d such that G can be realized as the intersection graph of a family of axis-parallel boxes in R^d. Boxicity is an important measure of structural complexity in various networks, including ecological and social systems. It also exhibits strong connections with other graph parameters such as treewidth, chromatic number, and vertex-cover number.

Determining the boxicity of a graph is computationally challenging—it is NP-hard to decide if a graph has boxicity at most 2. Consequently, much research has focused on developing efficient algorithms for specific graph classes or establishing upper bounds under particular conditions.

In this talk, we introduce a simple, general approach to determining the boxicity of a graph by studying its interval-order subgraphs. Our method leads to several new bounds, including those for Kneser graphs (confirming a conjecture by Caoduro and Lichev [Discrete Mathematics, Vol. 346, 5, 2023]), line graphs, complements of line graphs, and complements of block graphs. Notably, our approach also yields polynomial-time algorithms. In particular, we present an algorithm to compute the boxicity of complements of block graphs—marking the first non-trivial family for which boxicity can be computed in polynomial time.

This is joint work with Amna Adnan, Matthew Barclay, Josh Childs, Will Evans, Tao Gaede, and András Sebő.