I first came across that algorithm as the "Random minimum cut" algorithm. And recently a colleague was trying to pack a big quantity of small textures into one image file. Then it clicked - why not use Karger for this packing problem?
I don't know a good way to map this problem to a graph defined in order to minimize the wasted space between images.
Here I define the minimum cut as "the atlas with less blank filler pixels". So I need to generate a graph that represents a "distance" between images as an edge. Any suggestion on what type of distance to use?
Here is the first idea I had:
Given an image A(w, h) where w is width and h i height, if B(w', h') exists for w = w' or h = h' create an edge between A and B. (The same rule with a certain tolerance could be used, like + or - 1%).
I would be very surprised if I am the first one to think about this. So if anybody knows about anything similar that has been done, please do say so.