Abstract: This paper proposed a Two Dimension KPPCT (Two Dimension Radix-k Planted Plane Cubic Tree,TDKPPCT) encoding scheme towards the problem of the lower data rate of KPPCT dynamic graph encoding.This scheme firstly encrypted the original watermarking value using the RSA encryption algorithm,and then mapped the encrypted watermarking value to the TDKPPCT encoding structure,which was improved on the structure of KPPCT encoding scheme.And of course it expanded the range of the watermarking value.Theoretical analysis and experimental results show that this scheme improved the data rate but also had good space overload and robustness.