  Software watermarking has received considerable attention and was adopted by
the software development community as a technique to prevent or discourage
software piracy and copyright infringement. A wide range of software
watermarking techniques has been proposed among which the graph-based methods
that encode watermarks as graph structures. Following up on our recently
proposed methods for encoding watermark numbers $w$ as reducible permutation
flow-graphs $F[\pi^*]$ through the use of self-inverting permutations $\pi^*$,
in this paper, we extend the types of flow-graphs available for software
watermarking by proposing two different reducible permutation flow-graphs
$F_1[\pi^*]$ and $F_2[\pi^*]$ incorporating important properties which are
derived from the bitonic subsequences composing the self-inverting permutation
$\pi^*$. We show that a self-inverting permutation $\pi^*$ can be efficiently
encoded into either $F_1[\pi^*]$ or $F_2[\pi^*]$ and also efficiently decoded
from theses graph structures. The proposed flow-graphs $F_1[\pi^*]$ and
$F_2[\pi^*]$ enrich the repository of graphs which can encode the same
watermark number $w$ and, thus, enable us to embed multiple copies of the same
watermark $w$ into an application program $P$. Moreover, the enrichment of that
repository with new flow-graphs increases our ability to select a graph
structure more similar to the structure of a given application program $P$
thereby enhancing the resilience of our codec system to attacks.
