The Fréchet distance is arguably the most popular similarity measure for curves in computational geometry. It was first studied from an algorithmic perspective in 1991 by Helmut Alt and Michael Godau and has received considerable attention since then. In this talk I will outline some notable results in this line of research and end with some open problems. 

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).

The recognition problem for penny graphs, contact graphs of unit disks in the plane, has been known to be NP-hard since the work by Breu and Kirkpatrick in the 90s. In this talk we settle the complexity of the problem by showing it is exactly as hard as deciding truth in the existential theory of the reals (ER). We will also give an introduction and overview of the recent complexity class ER.