FO model checking of geometric graphs

DOI10.4230/LIPICS.IPEC.2017.19MaRDI QIDQ5111878zbMATH OpenFDO

Authors Petr Hliněný, Filip Pokrývka, Bodhayan Roy

Publication date 27 May 2020

zbMATH Keywords

intersection graphsmodel checkingfirst-order logicfixed-parameter tractabilityvisibility graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Specification and verification (program logics, model checking, etc.) (68Q60) Classical first-order logic (03B10) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• FO model checking on geometric graphs
• Current trends and new perspectives for first-order model checking (invited talk)
• FO model checking on map graphs

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• scientific article; zbMATH DE number 969067 (Why is no real title available?)
• Algorithms – ESA 2005
• Characterizing and recognizing weak visibility polygons
• Cleaning interval graphs
• 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
• Faster existential FO model checking on posets
• Fundamentals of parameterized complexity
• Hiding people in polygons
• Inapproximability of finding maximum hidden sets on polygons and terrains
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Linear time solvable optimization problems on graphs of bounded clique-width
• Linear-time recognition of circular-arc graphs
• Reducing prime graphs and recognizing circle graphs
• The Complexity of the Partial Order Dimension Problem
• Unit disk graph recognition is NP-hard
• Visibility Algorithms in the Plane

Cited in

(7)

• Current trends and new perspectives for first-order model checking (invited talk)
• FO model checking on geometric graphs
• First-order interpretations of bounded expansion classes
• FO model checking of interval graphs
• FO model checking on map graphs
• FO model checking of interval graphs
• Recovering sparse graphs

This page was built for publication: FO model checking of geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111878)