We present a new rate-distortion optimization algorithm based on graph-cuts that can encode efficiently the coefficients of a critically sampled or even redundant non orthogonal transform. The basic idea is to construct a specialized graph such that its minimum cut minimizes an energy functional. We propose to use the graph-cut mechanism for the minimization of the rate-distortion Lagrangian function. To this aim, we have designed a graph able to represent the decomposition subbands and take into consideration their correlations in a biorthogonal multiresolution representation. The method yields good compression results compared to the state-of-art JPEG2000 codec, as well as a general improvement in visual quality.