The obstructions of a minor-closed set of graphs defined by a context-free grammar
✍ Scribed by B Courcelle; G Sénizergues
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 979 KB
- Volume
- 182
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
We establish that the finite set of obstructions of a minor-closed set of graphs given by a hyperedge replacement grammar can be effectively constructed. Our proof uses an auxiliary result stating that the system of equations associated with a proper hyperedge replacement grammar has a unique solution.
--Hyperedge Replacement graph grammars.
--monadic second-order formulas. The paradigm of a specification by forbidden minors is Kuratowski's theorem saying that a graph is planar iff it does not contain K3,3 nor Ks as a minor. The graphs K3,3 and K5 are called the obstructions of the class of planar graphs.
Graph 9rammars specify graphs in a generative way, by rules building graphs from smaller ones. Monadic second-order formulas can be used to express characteristic properties like connectivity or the existence of cycles. In certain cases, these three types of definitions are equivalent. The following theorem is the basis of the present paper (the definitions will be given later).
Theorem (Courcelle [6]). Let L be a minor-closed set of graphs of bounded tree-width.