  We extend the powerful Pullback-Pushout (PBPO) approach for graph rewriting
with strong matching. Our approach, called \pbpostrong, exerts more control
over the embedding of the pattern in the host graph, which is important for a
large class of graph rewrite systems. In addition, we show that \pbpostrong is
well-suited for rewriting labeled graphs and certain classes of attributed
graphs. For this purpose, we employ a lattice structure on the label set and
use order-preserving graph morphisms. We argue that our approach is simpler and
more general than related relabeling approaches in the literature.
