Abstract of

Facial circuits of planar graphs and context-free languages

by Bruno Courcelle and Denis Lapoire

It is known that a language is context-free iff it is the set of borders of the trees of recognizable set, where the border of a (labelled) tree is the word consisting of its leaf labels read from left to right.

We give a generalization of this result in terms of planar graphs of bounded tree-width. Here the border of a planar graph is the word of edge labels of a path which borders a face for some planar
embedding. We prove that a language is context-free iff it is the set of borders of the graphs of a set of (labelled) planar graphs of bounded tree-width which is definable by a formula of monadic
second-order logic.