Random map generation with random territories

Hi guys. I am making a 3D MMO. I have an idea it’s a big map with random territories and cities. I thought something like that: The red areas are my territories. The territory with purple lines is the “new” territory. I need a thing to create that new territory. The brown lines are roads and the red circles are cities.
alt text

I need some ideas how to think about this problem. These maps need to be stored on the server. And need to incresed by the server. At the start i’ll have 1 or 2 territories but after a while i’ll need more and more. How can i add random parts to an existing terrain by server side?
I have a socket client-server architecture.

Thanks for the help!

not exactly what you wanted but maybe you can start from this.