algorithm: from adjacency list to visual map

I'm writing a Risk-like board game in java. A feature is that players can design their own maps which they store in a text file. The text file lists all territories (== countries) in the world map followed by their direct neighbors. The game then scans the file and creates a collection of the territories with their corresponding adjacency lists.

The next step would be to translate this graph into a graphical representation. That means I want to represent each territory by a rectangle or some other simple shape. I don't want to go into complex, edgy borders between territories yet. So basically the territories will look like some African or North American nations with horizontal and vertical borders.

Now my problem is: While it would be easy to visualize a graph where the borders are represented by drawn edges between them, I find it difficult to place the territories (== vertices) directly adjacent to each other. In other words the territories should "touch" each other, like in the real world.

In particular, it is difficult because of such places where 4 or more territories border with each other (Consider Four Corners in USA with Arizona, Colora开发者_高级运维do, New Mexico, and Utah).

Now I was wondering if anybody ever tried to do something similar or if there are even existing algorithms dealing with this problem. I would appreciate any help and creative input. Thanks!

If you can use a graph layout tool like graphviz to get a planar projection of your graph, then you can look into computing the voronoi diagram of the points on your graph, which you could then distort to make things more visually interesting. (You may also need to watch out to make sure that you don't end up changing the adjacency properties when you compute the voronoi diagram, since it depends on the relative spacing of the points. You will probably also have to detect places where an "ocean" cell will have to be inserted in order to make two territories non-adjacent.)

GMap is exactly what I want. They're combining a variety of techniques, including Voronoi diagrams (here's a paper on the algorithm). Now I just have to figure out how to get it...