Quendus: I'm not too bothered about inconsistent roughness if it makes sense, e.g. water, trees, natural rock formations. As you said though the walls are incongruous. I'll try out the noise on the hex points and I've got a few more ideas since you pointed it out to me.
The force-base graph drawing is by far the slowest part of it all (2-3 order of magnitude). In comparison the subgraph isomorphism algorithm used to find the patterns has exponential running time but barely appears in profiles. It takes only a few seconds for up to 30 rooms, but 100 rooms took two minutes and 95% of the time is the graph drawing.
At least force-based graph drawing is simple to implement though :^) If anyone knows of a better graph drawing algorithm that would be cool. I've already looked into Tutte embedding and that doesn't really work, some of the planar graph drawing algorithms force everything into a big triangle which isn't any good either.
I found the secret to making the graph drawing work is to apply the force draw after each substitution step (which is very slow relatively). I also have to make sure the inserted part of the graph isn't too tangled up by using an edge from the matched part of the host graph to transform the substitute graph (this roughly rotates the substitute graph into the right position). You also have to prune the potential subgraph matches so only rotated matches are allowed, a flipped match makes it all fall down.
Krice: My previous system used that kind of algorithm, it was hard to get cells out of it though which is why I changed to Voronoi. I also wanted a level of control over the structure of the levels, hence graph grammars. Although the Space Colonisation algorithms I've seen recently might be a good idea as well.
