Methods of converting an image to graph
I'm not an expert, but perhaps this recent survey can help you:

K. Santle Camilus, V. K. Govindan, A Review on Graph Based Segmentation;
I.J. Image, Graphics and Signal Processing, 2012, 5, 1-13

Abstract: ... The major
four categorizations we have employed for the purpose of
review are: graph cut based methods, interactive methods,
minimum spanning tree based methods and pyramid
based methods. This review not only reveals the pros in
each method and category but also explores its
limitations. ...