Definability equals recognizability for κ-outerplanar graphs

L. Jaffke, H.L. Bodlaender

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

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 linear time for graphs of bounded treewidth, which is known as Courcelle's Theorem [6]. These algorithms are constructed as finite state tree automata, and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. We prove this conjecture for κ-outerplanar graphs, which are known to have treewidth at most 3κ - 1 [2].

Original languageEnglish
Title of host publication10th International Symposium on Parameterized and Exact Computation, IPEC 2015, 16-18 September 2015, Patras, Greece
Place of Publications.l.
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages176-186
Number of pages11
ISBN (Electronic)9783939897927
DOIs
Publication statusPublished - 1 Nov 2015
Event10th International Symposium on Parameterized and Exact Computation (IPEC 2015) - Patras, Greece
Duration: 16 Sep 201518 Sep 2015
Conference number: 10
http://algo2015.upatras.gr/ipec

Conference

Conference10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Abbreviated titleIPEC 2015
CountryGreece
CityPatras
Period16/09/1518/09/15
Internet address

Keywords

  • Finite state tree automata
  • Monadic second order logic of graphs
  • Treewidth
  • κ-outerplanar graphs

Cite this