Seminars

Interval graphs arise as intersection graphs of intervals on the real line and form a natural meeting point between discrete geometry and graph theory. Their rich structure yields efficient algorithms and applications in scheduling and resource allocation. Representing graphs as intersection graphs of axis-aligned boxes in R^d extends this idea to higher dimensions; the minimum dimension required is the boxicity of the graph, introduced by Roberts in 1969. Boxicity models competition for shared resources in ecology and operations research. It also matters algorithmically: graphs of bounded boxicity inherit some of the tractability of interval graphs (for example, Maximum Clique remains polynomial-time solvable). Exploiting this, however, typically requires a box representation, and finding one is NP-hard in general. Only a few graph classes are known for which boxicity can be computed in polynomial time. To extend this list and to develop new techniques for the problem, we follow the approach of Cozzens and Roberts (1983) and study the boxicity of a graph's complement, which we call its co-boxicity. This change of perspective trades d-dimensional boxes for one-dimensional objects: the co-boxicity of a graph is the minimum number of co-interval subgraphs needed to cover its edges. We show that co-boxicity can be computed block by block from a small amount of local information. As corollaries, we obtain a fixed-parameter tractable algorithm parameterized by the size of the largest block, and polynomial-time algorithms for block graphs and cactus graphs. This talk presents joint work with Will Evans and Tao Gaede.