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

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2017.19

zbMATH Keywords

first-order logicfixed-parameter tractabilityintersection graphsmodel checkingvisibility graphs

Mathematics Subject Classification ID

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

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

• 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
• Faster existential FO model checking on posets
• FO model checking of interval graphs
• Fundamentals of parameterized complexity
• Hiding people in polygons
• 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?)
• 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

(8)

• FO model checking on geometric graphs
• FO model checking on map graphs
• FO model checking of interval graphs
• First-order interpretations of bounded expansion classes
• Recovering sparse graphs
• Current trends and new perspectives for first-order model checking (invited talk)
• FO model checking of interval graphs
• Model checking disjoint-paths logic on topological-minor-free graph classes

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)