  Graph transformation is the rule-based modification of graphs, and is a
discipline dating back to the 1970s. In general, to match the left-hand graph
of a fixed rule within a host graph requires polynomial time, but to improve
matching performance, D\"orr proposed to equip rules and host graphs with
distinguished root nodes. This model was implemented by Plump and Bak, but
unfortunately, such rules are not invertible. We address this problem by
defining rootedness using a partial function into a two-point set rather than
pointing graphs with root nodes, meaning derivations are natural double
pushouts. Moreover, we give a sufficient condition on rules to give constant
time rule application on graphs of bounded degree, and that, the graph class of
trees can be recognised in linear time, given an input graph of bounded degree.
Finally, we define a new notion of confluence up to garbage and non-garbage
critical pairs, showing it is sufficient to require strong joinability of only
the non-garbage critical pairs to establish confluence up to garbage. Finally,
this new result, presented for conventional graph transformation systems, can
be lifted to our rooted setting by encoding node labels and rootedness as
looped edges.
