MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree $k$-Outerplanar Graphs

Lars Jaffke, Hans L. Bodlaender

One of the most famous algorithmic meta-theorems states that every graph property that can be defined by a sentence in counting monadic second order logic (CMSOL) can be checked in…