In this talk, we'll introduce graph wedgelets as an adaptive tool for data compression on graphs. Graph wedgelets approximate signals on graphs by piecewise constant functions on adaptively generated binary wedge partitionings. In particular, they are discrete variants of continuous wedgelets and binary space partitionings that are frequently used for the compression of 2D images. We prove that continuous results on best m-term approximation with geometric wavelets can be transferred to the discrete graph setting and show that the wedgelet representation of graph signals can be encoded and implemented in a simple way by a binary tree structure. We will also illustrate how this graph-based method can be applied for the compression and segmentation of images.