License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.175
URN: urn:nbn:de:0030-drops-55815
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5581/
Go to the corresponding LIPIcs Volume Portal

Jaffke, Lars ; Bodlaender, Hans L.

Definability Equals Recognizability for k-Outerplanar Graphs

pdf-format:
18.pdf (0.6 MB)

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. 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 k-outerplanar graphs, which are known to have treewidth at most 3k-1.

BibTeX - Entry

@InProceedings{jaffke_et_al:LIPIcs:2015:5581,
  author =	{Lars Jaffke and Hans L. Bodlaender},
  title =	{{Definability Equals Recognizability for k-Outerplanar Graphs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{175--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5581},
  URN =		{urn:nbn:de:0030-drops-55815},
  doi =		{10.4230/LIPIcs.IPEC.2015.175},
  annote =	{Keywords: treewidth, monadic second order logic of graphs, finite state tree automata, $k$-outerplanar graphs}
}

Keywords: treewidth, monadic second order logic of graphs, finite state tree automata, $k$-outerplanar graphs
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI