<p><a href="http://www.cs.arizona.edu/~kobourov/PROJECTS/maps.html" rel="nofollow">GMap</a> is exactly what I want. They're combining a variety of techniques, including Voronoi diagrams (<a href="http://arxiv.org/pdf/0907.2585v1" rel="nofollow">here's a paper on the algorithm</a>). Now I just have to figure out how to get it...</p>
algorithm: from adjacency list to visual map
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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, Colorado, New Mexico, and Utah).</p>

<p>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!</p>