Marco Caoduro est chercheur postdoctoral à Sauder School of Business, UBC, Canada.
Title : Boxicity: How Many Dimensions Does a Graph Need?
Abstract : Abstract:
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 strong structural properties yield efficient algorithms and natural applications in scheduling and resource allocation. A natural higher-dimensional generalization is to represent graphs as intersection graphs of axis-aligned boxes in ℝᵈ; the minimum such dimension is the boxicity, introduced by Roberts in 1969.
Graphs of bounded boxicity retain much of the algorithmic tractability of interval graphs: problems that are NP-hard in general often become polynomial-time solvable or better approximable for graphs of low boxicity. Beyond algorithmic motivation, boxicity also appears in ecology and operations research.
In this talk, I present structural and algorithmic results on boxicity. I describe a general method based on interval-order subgraphs that provides a unified framework for bounding and determining boxicity. This approach yields exact values for several classical graphs, including the Petersen graph and the Kneser graphs K(n,2), and extends to broader families related to line graphs. Although computing boxicity is NP-hard in general, I will also discuss polynomial-time algorithms for complements of block graphs and for their threshold dimension, another related dimensional parameter. Finally, I highlight connections with algebraic constructions, including zero-divisor graphs, which have become an active area of investigation.
This talk presents joint work with Will Evans, Tao Gaede, Lyuben Lichev, Meike Neuwohner, and András Sebő, drawing on results from several collaborative projects.
Web site : https://marcocaoduro.com/