THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .6. ON SEVERAL REPRESENTATIONS OF GRAPHS BY RELATIONAL STRUCTURES

The same properties of graphs of degree at most k, where k is a fixed integer, can be expressed by monadic second-order formulas using edge and vertex quantifications as well as by monadic second-order formulas using vertex quantifications only. It is also proved that, for expressing properties of undirected graphs, an auxillary orientation does not increase the expressive power of monadic second-order logic. Similar results hold for partial k-trees (for fixed k), for planar graphs, and more generally, for the graphs that do not contain some fixed graph as a minor. These results are related with the possibility of testing graph properties in polynomial time for graphs generated by context-free graph-grammars of various types.