FO model checking of geometric graphs

DOI10.4230/LIPICS.IPEC.2017.19zbMATH Open1443.68105MaRDI QIDQ5111878FDOQ5111878

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

Publication date: 27 May 2020

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Unit disk graph recognition is NP-hard
• Linear-time recognition of circular-arc graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Title not available (Why is that?)
• Title not available (Why is that?)
• Interpreting nowhere dense graph classes as a classical notion of model theory
• The Complexity of the Partial Order Dimension Problem
• Visibility Algorithms in the Plane
• Deciding first-order properties of locally tree-decomposable structures
• Reducing prime graphs and recognizing circle graphs
• Algorithms – ESA 2005
• Cleaning interval graphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Title not available (Why is that?)
• Hiding people in polygons
• Characterizing and recognizing weak visibility polygons
• Computing the maximum clique in the visibility graph of a simple polygon
• FO model checking of interval graphs
• Faster existential FO model checking on posets
• Inapproximability of finding maximum hidden sets on polygons and terrains

Cited In (7)

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

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)