Geometry Seminar

---

Compact Representations

Speaker: Jean Cardinal, Université libre de Bruxelles

Location: Online

Date: Tuesday, March 31, 2026, 2 p.m.

Synopsis:

In computational geometry, one often meets graphs representing various kinds of geometric relations: intersection, containment, incidence, visibility, etc. While these graphs have natural geometric representations, these representations might sometimes be costly. We will consider biclique decompositions of such graphs, that allow compact representations using o(n) bits per vertex. In particular, we will describe compact representations of semialgebraic graphs - including segment and disk intersection graphs, semilinear graphs - including intersection graphs of rectilinear geometric objects, and various flavors of visibility graphs. We will argue that such representations are practical alternatives to the usual adjacency list representations. The presentation will involve classical and more recent results, including a joint work with Yelena Yuditsky (ESA 2025).

Notes:

On Zoom.  Please contact Boris Aronov to be put on the email announcement list and obtain Zoom details.