FO model checking on geometric graphs
DOI10.1016/j.comgeo.2018.10.001zbMath1453.68102arXiv1709.03701OpenAlexW2964004645WikidataQ129079546 ScholiaQ129079546MaRDI QIDQ1631773
Bodhayan Roy, Filip Pokrývka, Petr Hliněný
Publication date: 7 December 2018
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1709.03701
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Specification and verification (program logics, model checking, etc.) (68Q60) Classical first-order logic (03B10) Graph representations (geometric and intersection representations, etc.) (05C62) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Induced subgraph isomorphism on proper interval and bipartite permutation graphs
- Characterizing and recognizing weak visibility polygons
- Reducing prime graphs and recognizing circle graphs
- Hiding people in polygons
- Unit disk graph recognition is NP-hard
- Linear-time recognition of circular-arc graphs
- Generalized guarding and partitioning for rectilinear polygons
- Cleaning interval graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Interpreting nowhere dense graph classes as a classical notion of model theory
- Computing the maximum clique in the visibility graph of a simple polygon
- Deciding first-order properties of locally tree-decomposable structures
- FO Model Checking of Interval Graphs
- Recognizing visibility graphs of spiral polygons
- The Complexity of the Partial Order Dimension Problem
- On Comparability and Permutation Graphs
- Model checking existential logic on partially ordered sets
- A New Perspective on FO Model Checking of Dense Graph Classes
- Deciding First-Order Properties of Nowhere Dense Graphs
- Testing first-order properties for subclasses of sparse graphs
- Visibility Algorithms in the Plane
- Algorithms – ESA 2005
- Faster Existential FO Model Checking on Posets
- Inapproximability of finding maximum hidden sets on polygons and terrains
