Definability Equals Recognizability for $k$-Outerplanar Graphs

DOI10.4230/LIPIcs.IPEC.2015.175zbMath1378.03032arXiv1509.08315OpenAlexW2223243427MaRDI QIDQ5363771

Lars Jaffke, Hans L. Bodlaender

Publication date: 29 September 2017

Full work available at URL: https://arxiv.org/abs/1509.08315

zbMATH Keywords

treewidth\(k\)-outerplanar graphsmonadic second-order logic of graphsfinite-state tree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05)

Related Items (5)

Recognizability equals definability for graphs of bounded treewidth and bounded chordality ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Unnamed Item ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity ⋮ Causality in Bounded Petri Nets is MSO Definable

This page was built for publication: Definability Equals Recognizability for $k$-Outerplanar Graphs