2026-09-05T11:58:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25857 2026-06-23T12:59:41Z ddc:004 open_access

First-Order Logic and Twin-Width for Some Geometric Graphs Geniet, Colin Kim, Gunwoo Meijer, Lucas Twin-width axis-parallel unit segment graphs circular arc graphs terrain visibility graphs first-order logic model checking FPT 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Colin Geniet and Gunwoo Kim and Lucas Meijer 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.51 urn:nbn:de:0030-drops-258575 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.51 eng https://creativecommons.org/licenses/by/4.0/legalcode