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.
Summary
This paper investigates the relationship between first-order (FO) logic tractability and the graph parameter twin-width for geometric graphs. The central research question is whether twin-width precisely characterizes the tractability of FO model checking for specific geometric graph classes, a property termed "delineation." The authors extend previous work showing that delineation holds for several graph classes by focusing on intersection graphs of geometric objects. The methodology involves proving a dichotomy: either a graph class has bounded twin-width (and therefore FPT FO model checking) or it is monadically independent (and therefore FO model checking is AW[*]-hard). This is achieved by constructing auxiliary matrices from geometric representations of the graphs. The presence of a grid in these matrices is then linked to either bounded twin-width or the existence of a "transversal pair," which implies monadic independence. The authors provide new proofs to show that delineation holds for intersection graphs of non-degenerate axis-parallel unit segment graphs and circular arc graphs. They also demonstrate that delineation fails for visibility graphs of 1.5D terrains and other variants of axis-parallel segment graphs. The key contribution is the extension of delineation results to new geometric graph classes and the identification of cases where delineation fails. This matters to the field because it provides a deeper understanding of the connection between structural graph parameters, logical expressibility, and algorithmic complexity for geometric graphs. The results contribute to the ongoing effort to understand Conjecture 5, which posits a general equivalence between FPT FO model checking and monadic dependence.
Key Insights
- •Delineation holds for intersection graphs of non-degenerate axis-parallel unit segments (APUS) and circular arc graphs, answering open questions from previous work.
- •Delineation fails for visibility graphs of 1.5D terrains, showing that the relationship between twin-width and FO model checking can break down even for relatively simple geometric graph classes.
- •The authors introduce a technique of splitting APUS graphs into local regions (unit squares) and analyzing the twin-width of each region independently.
- •They demonstrate that even when delineation fails, classes with unbounded twin-width may still have FPT FO model checking due to bounded merge-width.
- •The paper shows that a minimized circular arc representation's endpoint matrix can be used to find transversal pairs, thus showing monadic independence and AW[*]-hardness for FO model checking.
- •Theorem 10, using edge partitions preserves bounded twin-width, but does require ordered graphs.
- •The paper provides a counterexample (Theorem 4) showing that delineation fails for H-graphs when H is a connected graph with at least two cycles.
Practical Implications
- •The results have implications for algorithm design in areas such as computational geometry, graph databases, and knowledge representation. If a problem can be expressed as FO model checking on a graph class known to have bounded twin-width, then an efficient (FPT) algorithm is guaranteed.
- •Practitioners working with geometric data can use the delineation results to determine whether FO queries can be answered efficiently based on the structural properties of the underlying graph.
- •The paper highlights the importance of considering the specific properties of geometric graphs when designing algorithms for FO model checking. Assumptions such as non-degeneracy of segments can significantly impact the complexity of the problem.
- •Future research directions include investigating delineation for other geometric graph classes such as unit-disk graphs, and exploring the relationship between merge-width and monadic dependence for geometric graphs.