FO model checking of geometric graphs

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

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

Publication date: 27 May 2020

Recommendations

• FO model checking on geometric graphs
• A New Perspective on FO Model Checking of Dense Graph Classes
• A New Perspective on FO Model Checking of Dense Graph Classes
• 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?)
• Deciding First-Order Properties of Nowhere Dense Graphs
• 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
• Model checking existential logic on partially ordered sets
• A New Perspective on FO Model Checking of Dense Graph Classes
• Faster Existential FO Model Checking on Posets
• Inapproximability of finding maximum hidden sets on polygons and terrains

Cited In (4)

• FO model checking on geometric graphs
• A New Perspective on FO Model Checking of Dense Graph Classes
• Title not available (Why is that?)
• Title not available (Why is that?)

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)