  Watermarking is a way of embedding information in digital documents. Much
research has been done on techniques for watermarking relational databases and
XML documents, where the process of embedding information shouldn't distort
query outputs too much. Recently, techniques have been proposed to watermark
some classes of relational structures preserving first-order and monadic second
order queries. For relational structures whose Gaifman graphs have bounded
degree, watermarking can be done preserving first-order queries.
  We extend this line of work and study watermarking schemes for other classes
of structures. We prove that for relational structures whose Gaifman graphs
belong to a class of graphs that have locally bounded tree-width and is closed
under minors, watermarking schemes exist that preserve first-order queries. We
use previously known properties of logical formulas and graphs, and build on
them with some technical work to make them work in our context. This
constitutes a part of the first steps to understand the extent to which
techniques from algorithm design and computational learning theory can be
adapted for watermarking.
