  Digital watermarks have been considered a promising way to fight software
piracy. Graph-based watermarking schemes encode authorship/ownership data as
control-flow graph of dummy code. In 2012, Chroni and Nikolopoulos developed an
ingenious such scheme which was claimed to withstand attacks in the form of a
single edge removal. We extend the work of those authors in various aspects.
First, we give a formal characterization of the class of graphs generated by
their encoding function. Then, we formulate a linear-time algorithm which
recovers from ill-intentioned removals of $k \leq 2$ edges, therefore proving
their claim. Furthermore, we provide a simpler decoding function and an
algorithm to restore watermarks with an arbitrary number of missing edges
whenever at all possible. By disclosing and improving upon the resilience of
Chroni and Nikolopoulos's watermark, our results reinforce the interest in
regarding it as a possible solution to numerous applications.
