I've been trying to do this for a long long time, but am completely stumped.
Can polyominoes actually be represented as graphs, without using an entire face of the graph for each square?
I've tried to find some way to map squares to either vertices, or edges, but the problem of things like I/S/L-blocks ending up as the same thing always crops up.