BARC talk by Lucas Meijer

Thursday, April 30, 2026, 14:00-15:00, Lucas Meijer, PhD student at Utrecht University, The Netherlands, will be giving a BARC talk on "First-Order Logic and Twin-Width for Some Geometric Graphs".

Abstract:
For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval graphs among others in [BCKKLT, IPEC '22], where the equivalence is called delineation, and more generally holds for circle graphs, rooted directed path graphs, and H-graphs when H is a forest. Delineation is based on the key idea that geometric graphs often admit natural vertex orderings, allowing to use the very rich theory of twin-width for ordered graphs.
Answering two questions raised in their work, we prove that delineation holds for intersection graphs of non-degenerate axis-parallel unit segment graphs, but fails for visibility graphs of 1.5D terrains. We also prove delineation for intersection graphs of circular arcs.

This is joint work with Colin Geniet and Gunwoo Kim.

Bio:
Lucas Meijer is a PhD student at Utrecht University supervised by Till Miltzow. He enjoys working on a variety of topics within theoretical computer science, notably including the Existential Theory of the Reals, where he has worked on both completeness proof and the complexity-theoretic relations to other classes. Other topics he has worked on include fine-grained analysis, geometric algorithms, reconfiguration algorithms, and parametrized algorithms.

Host:
Mikkel Abrahamsen