Abstracts for the LGTDS workshop

ICGT Conference , Barcelona, October 2002

Finite Model Theory characterization of some graph grammars

Alex Glikson


(joint work with J. Makowsky, janos@cs.technion.ac.il )


There are several graph sparsity conditions, that allow polynomial recognition and/or model-checking over graphs and hypergraphs. Two of them are tree-width and clique-width. We examine graph classes generated by various graph grammars and other grammar-like methods. Although most of them are already known to be of bounded tree-width/
clique-width, for some of them no strait-forward way to find these bounds is known. We use several old and recent techniques in order to classify these classes and to find explicitly the bounds for tree-width and clique-width of corresponding graphs.