  We introduce graph wedgelets - a tool for data compression on graphs based on
the representation of signals by piecewise constant functions on adaptively
generated binary graph partitionings. The adaptivity of the partitionings, a
key ingredient to obtain sparse representations of a graph signal, is realized
in terms of recursive wedge splits adapted to the signal. For this, we transfer
adaptive partitioning and compression techniques known for 2D images to general
graph structures and develop discrete variants of continuous wedgelets and
binary space partitionings. We prove that continuous results on best m-term
approximation with geometric wavelets can be transferred to the discrete graph
setting and show that our wedgelet representation of graph signals can be
encoded and implemented in a simple way. Finally, we illustrate that this
graph-based method can be applied for the compression of images as well.
