Delineation of unit segment graphs by twin-width

Open Question (unit segment graphs delineation) · arXiv:2204.00722

arXiv Question high confidence— first stated 2022-04-01

Authors: Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé

Status partial medium confidence

The open question of whether unit segment graphs are delineated (by twin-width) remains unresolved for the general class, but significant partial progress has been made. Geniet, Kim, and Meijer (arXiv:2512.21896, 2025) prove that delineation holds for intersection graphs of non-degenerate axis-parallel unit segment graphs, while also showing that delineation fails for visibility graphs of 1.5D terrains; additionally the paper's body discusses non-delineation for more general unit segment variants (degenerate axis-parallel and arbitrary-slope unit segments). The non-degenerate axis-parallel subcase is thus settled positively, but the status of the full class of unit segment graphs — as posed in arXiv:2204.00722 — remains unresolved or at best partially answered negatively for broader subclasses.

Cited literature (1)

partial First-Order Logic and Twin-Width for Some Geometric Graphs (2025)

Colin Geniet, Gunwoo Kim, Lucas Meijer · arXiv preprint · arXiv:2512.21896

Proves that delineation holds for non-degenerate axis-parallel unit segment graphs, and that delineation fails for visibility graphs of 1.5D terrains; the paper also establishes non-delineation for degenerate axis-parallel and arbitrary-slope unit segment variants, leaving the general unit segment graph question in a nuanced state.

Reviewer notes. The 2025 paper arXiv:2512.21896 makes the most direct progress on this question: it settles the non-degenerate axis-parallel case positively (delineated) but the body of the paper reportedly shows non-delineation for general/degenerate unit segment graphs. Bonnet's open problems page (perso.ens-lyon.fr/edouard.bonnet/openQuestions.html) still lists the question as open. Confidence is medium because the full-paper content was accessed via HTML rendering which may not capture all nuance; the abstract clearly establishes only the positive partial result for non-degenerate axis-parallel unit segment graphs.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Are unit segment graphs delineated (by twin-width)?

Context

The paper establishes that axis-parallel $H_t$-free unit segment graphs have bounded twin-width, while axis-parallel $H_4$-free two-lengthed segment graphs have unbounded twin-width, and that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width. This places unit segment graphs at the frontier between delineated and non-delineated intersection graph classes, and the authors explicitly leave their delineation status as an open question.

Notes. Stated verbatim in the abstract: 'We leave as an open question whether unit segment graphs are delineated.'

Source paper

Twin-width VIII: delineation and win-wins
Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Noleen Köhler, Raul Lopes, Stéphan Thomassé · 2022-04-01
https://arxiv.org/abs/2204.00722 PDF source