Over on RPGnet, Roger posted about his experiments with running minimal prep games. He jokingly refers to this as "slackbox", in contrast to "sandbox"; what he wants is the "go anywhere, do anything" feel of sandbox games without the heavy prep that many sandbox advocates do. His PDF is interesting reading, especially when he reduces mapping tasks to just getting a bunch of points (representing towns and dungeons,) laying them on top of a bunch of "blobs" or zones (representing terrain features,) and connecting some points with lines representing roads or rivers.
The "random sandbox generation system" that I've talked about before (ages ago, it seems...) is kind of similar in some ways: generate land features (the "blobs") and a river, then generate kingdom codes defining which river the tiny kingdoms are located along, where they are on the river, and how many cities the kingdom has. Names are assigned afterwards. The difference is that I use a system that generates sketches -- literal sketch maps, but also sketchy details for each terrain feature, kingdom, or city. I roll dice on a sheet of paper and sketch out where they land in four layers: high terrain (mountains or hills,) low terrain (probably where large bodies of water will be,) other terrain (forests or whatever,) and rivers. I then roll to find out how many kingdoms are along each river and where they are located, then 1 to 3 facts per "thing" to tell me what makes that feature, kingdom, or city different. It creates settings I feel are good for minimal prep settings that grow during play.
I think of this as sandbox play, but since so many of the sandbox advocates use the term for heavy-prep open-ended settings, perhaps it needs a different name. In the linked thread, OneEyedMan suggests "sketchbox". I suppose that's good enough for now.